共计 2152 个字符，预计需要花费 6 分钟才能阅读完成。
例题：缺失的第一个正数
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
原地 Hash
例题：
缺失的第一个正数
难度：hard
描述
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例
示例 1：
输入：[1,2,0]
输出：3示例 2：
输入：[3，4，-1，1]
输出：2示例 3：
输入：[7,8,9,11,12]
输出：1要求
你的算法的时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。
分析与题解
如果不看要求的话题目是非常简单的，直接使用一个 HashMap 就可以了（HashSet 也是一个 HashMap 的实例）。如下所示：
class Solution {public int firstMissingPositive(int[] nums) {Set<Integer> set = new HashSet<>();
// 只有 [1,n] 范围的数据有效
for (int num: nums){if (num>0 && num<=nums.length){set.add(num);
}
}
// 找到第一个未出现过的正数
for (int i=1; i<=nums.length; ++i){if (!set.contains(i)){return i;}
}
return nums.length+1;
}
}然而，虽然时间复杂度只有 O(N)，空间复杂却因为 HashMap 的原因随着数组的增加线性增长，也是 O(N)。不满足题目的常数级别的额外空间要求。
这时候，让我们重新审题，看看能不能从哪里找到突破口：
一个 未排序 的数组，要求在 O(N) 的时间复杂度 以及 O(1) 的空间复杂度 的情况下，找到缺失的 第一个正整数。
重新看这个题目，重要条件无外乎上面四个粗体字。
要求找到的这个第一个正整数就是我们的答案，而正整数不正是从 1 一开始的一个数组吗。如果是已经 排序好了 的数组，我们可以直接从 1 开始查找，在 [1,n+1] 的范围内一定可以找到缺失的正整数（数组一共只有 n 个数字）。但是题目明确说明了数组是未排序的，而已知的任何一个排序算法都无法做到 O(N)的时间复杂度。排序再查找是不可行的！
但是我们需要排序吗？
不需要！因为我们只用找到第一个没有出现的元素就行了。因此，我们可以在这个角度考虑：常数级的空间复杂度要求我们不能创建一个新的数组。如果要对数字的顺序进行变化，就只能在 原数组进行。那如何变化才能找到第一个没有出现的正整数呢？
我们继续思考给定数组与题目要求结果的联系：数组下标范围[0,n-1]，题目结果[1,n+1]。
现在问题很简单了。我们是不是只需要将数组中满足题目要求的元素，放到对应下标。最后遍历一遍数组，看哪个下标没有对应的元素，不就是答案了吗？
具体代码如下
class Solution {public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i=0; i<len; ++i){// 这里注意两个元素交换之后，nums[i]还是没有回到应该在的位置
// 比如[1,2,0]，在第一次交换之后[2,1,0]，2 这个元素不应该在这个位置，因此需要循环直到下标为 0 的元素归位
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {swap(nums,nums[i] - 1, i);
}
}
for (int i=0; i<len; ++i){if (nums[i]!=i+1){return i+1;}
}
return len+1;
}
public static void swap(int[] nums, int i, int j){int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}官方给了一个更为巧妙的解法：通过将所有负数转为 len+ 1 之后，将满足条件的元素转化为绝对值的负数。最后遍历找到第一个正数。不再需要交换元素
详情见：https://leetcode-cn.com/probl…
class Solution {public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {if (nums[i] <= 0) {nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {int num = Math.abs(nums[i]);
if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}
}
return n + 1;
}
}总结与反思
这题感觉并没有 hard 难度，因为思想其实挺简单的。无非是将键值对之间的巧妙联系起来，然而我还是学到了许多。
这几天看了遍 hashmap 的源码，自认为对 hashmap 学得挺通透了的。却被力扣的这个每日一题打了脸，稀里糊涂地做出来之后，去看题解才反应过来——噢，这原来是自己写了一个定制的 hash 函数啊。一直有在提醒自己不要画地为牢，却还是进入了惯性思维：以为 hash 就是源码那些 f(x)=n&(length-1)。还是需要多做题，理解思想，而不是仅仅会学而已。
