41. 缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目要求：时间复杂度为 O(n) 并且只使用常数级别额外空间，这也是为什么是困难题的原因。

因此，只能遍历常数次数组，不使用额外空间的一种思路是修改原数组。

记数组长度为n，可以发现，如果数组元素分别是1到n，那么缺失的第一个正数为n+1；而如果不是的话，第一个正数一定小于等于n。

可以先遍历数组，将介于1到n之间的数num放置到数组的num-1下标，而对于不在1到n之间的数则跳过。

然后再一次遍历数组，遇到第一个不满足num==i+1的num就是第一个缺失的正数。而如果所有数都满足的话，缺失的就是n+1

代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 将介于[1,n]的nums[i]放置到下标nums[i]-1处
            // 注意交换的两个数不能相等，否则会死循环
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        // 返回第一个不满足num==i+1的num
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 数组元素分别是1到n，那么缺失的第一个正数为n+1
        return n + 1;
    }
}