原地Hash

例题：缺失的第一个正数

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

缺失的第一个正数

难度：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)。还是需要多做题，理解思想，而不是仅仅会学而已。

原地 Hash

例题：

描述

示例

要求

分析与题解

总结与反思