题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ – 1

解法

解法一 HashSet保存是否出现

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 用HashSet来存放
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int result = 1;
        while (result <= Integer.MAX_VALUE) {
            if (!set.contains(result)) return result;
            result++;
        }
        return 0;
    }
}

时间复杂度为O(N)，但是空间复杂度同样为O(N)，不符合O(1)的要求。

解法二 在原数组上打标记🏷️

参考leetcode官方题解

缺失的第一个正数一定在nums数组长度之内（最大是length + 1），所以可以考虑在原数组中加上易识别的“标记”🏷️

怎样来实现标记呢？

用负号作为标记！每当遍历到正数i时候，就将nums[i]置为负数，而原本数组中的负数应该变成不影响识别的正数，比如不在范围内的length+1。

最后遍历一次找到第一个正数的index即为结果。

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 在对应index上标记表示这个数字是否出现过 比如用负数作为标记
        // 消除原数组干扰 - 原本是负数或0就将其置为 nums.length(不会造成干扰)
        int safeNum = nums.length + 1;
        for (int i = 0; i < nums.length; i++) 
            if (nums[i] <= 0) nums[i] = safeNum;
        for (int i = 0; i < nums.length; i++) {
            int absOfNum = Math.abs(nums[i]);
            if (absOfNum < safeNum) nums[absOfNum - 1] = -1 * Math.abs(nums[absOfNum - 1]);
        }
        // 找出第一个不是负数的index
        int result = 0;
        while (result < nums.length && nums[result] <= 0) result++;
        return result + 1;
    }
}

因为是在原数组操作，空间复杂度为O(1)。符合要求

解法三 置换法

略

小结

解法二的思路值得借鉴。

空间复杂度要求O(1)的时候，可能要求原地操作，就要积极的考虑打标记的方法。思考如何利用原数组的信息做标记（利用index作为信息等）。

本题是将原本无用的负数处理后，用负数作为标记。