【Hot 100 刷题计划】 LeetCode 41. 缺失的第一个正数 | C++ 原地哈希题解

张开发
• 2026/4/8 15:31:17 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【Hot 100 刷题计划】 LeetCode 41. 缺失的第一个正数 | C++ 原地哈希题解
LeetCode 41. 缺失的第一个正数 | C 哈希表基础解法 题目描述题目级别困难 (Hard)给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。示例 1:输入nums [1,2,0]输出3解释范围 [1,2] 中的数字都在数组中。示例 2:输入nums [3,4,-1,1]输出2解释1 在数组中但 2 没有。 解法一常规哈希表 (直觉解法空间 O(N))寻找“缺失的数字”最符合人类直觉的方法就是把见过的数字都记在小本本上然后从 1 开始挨个往上数看看谁没被记过。在代码实现中这个“小本本”最合适的数据结构就是哈希集合unordered_set。遍历原数组把所有的正整数都扔进unordered_set中记录下来自动去重且查找时间为O(1)O(1)O(1)。初始化一个目标值target 1不断递增去哈希表里查。查不到的那个数字就是缺失的第一个正数 C 代码实现classSolution{public:intfirstMissingPositive(vectorintnums){// 使用哈希集合记录所有出现过的正整数unordered_setintseen;for(intnum:nums){if(num0){seen.insert(num);}}// 从 1 开始逐个检查谁没出现过inttarget1;while(true){// 如果在哈希表中找不到 target说明这就是缺失的最小正数if(seen.find(target)seen.end()){returntarget;}target;}}}; 解法二原地哈希 / 循环排序 (面试满分终极解空间 O(1))题目给出了极其严苛的条件时间O(N)O(N)O(N)且空间O(1)O(1)O(1)。这意味着我们不能开辟新的哈希表只能把原数组本身当作哈希表来用对于一个长度为NNN的数组它里面能装下的“连续正数”最多也就是1, 2, 3... N。如果数组里装满了1到N那缺失的正数就是N 1如果不满缺失的正数一定在[1, N]之间。因此我们可以制定一个规矩数字i必须老老实实呆在索引i - 1的位置上即数字 1 放在索引 0数字 2 放在索引 1…。这就好比“一个萝卜一个坑”。操作步骤数字归位遍历数组只要当前萝卜数字是个有效正数且没呆在正确的坑位上我们就把它交换到它该去的地方。换过来的新萝卜如果也不对就继续换。查岗核对等所有萝卜都归位了我们再从头巡查一遍。如果发现哪个坑里装的不是正确的萝卜那个坑对应的数字就是缺失的 C 代码实现classSolution{public:intfirstMissingPositive(vectorintnums){intnnums.size();// 第一阶段将所有在 [1, n] 范围内的萝卜归位for(inti0;in;i){// 只要当前数字是有效正数且不在正确的坑位上就不断进行交换while(nums[i]0nums[i]nnums[i]!nums[nums[i]-1]){// 将 nums[i] 送回到属于它的索引位置 (nums[i] - 1)swap(nums[i],nums[nums[i]-1]);}}// 第二阶段查岗寻找第一个坑位不对的数字for(inti0;in;i){// 索引 i 应该对应数字 i 1if(nums[i]!i1){returni1;// 找到了缺失的最小正数}}// 如果 1 到 n 都整整齐齐排好了那缺失的就是 n 1returnn1;}};

更多文章