例题：缺失的第一个正数来源：力扣（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)。还是需要多做题，理解思想，而不是仅仅会学而已。