41 缺失的第一个正数

一、题目

41. 缺失的第一个正数

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

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

二、题解

原地哈希 / 原地交换

思路：把数字放到它应该在的位置上

数组长度为 n，缺失的第一个正数一定在：1 ~ n + 1

例如数组长度是 4，答案只可能是：1, 2, 3, 4, 5

我们希望把每个正整数 x 放到下标 x - 1 的位置。

也就是：

数字 1 应该放到 nums[0]
数字 2 应该放到 nums[1]
数字 3 应该放到 nums[2]
...
数字 x 应该放到 nums[x - 1]

处理完成后，再从左到右扫描数组：

如果 nums[i] != i + 1
说明 i + 1 这个正整数缺失

如果全部都对，那么答案就是 n + 1。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 把每个在 [1, n] 范围内的数字，放到它应该在的位置上
        for (int i = 0; i < n; i++) {

            /*
             * nums[i] 应该放到 nums[nums[i] - 1] 的位置
             *
             * 需要满足：
             * 1. nums[i] 是正数
             * 2. nums[i] <= n，因为大于 n 的数字不用管
             * 3. nums[i] 还没有放到正确位置，避免死循环
             */
            while (
                nums[i] >= 1 &&
                nums[i] <= n &&
                nums[i] != nums[nums[i] - 1]
            ) {
                swap(nums, i, nums[i] - 1);
            }
        }

        // 从左到右找第一个位置不匹配的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 如果 1 ~ n 都存在，那么缺失的就是 n + 1
        return n + 1;
    }

    // 交换数组中两个位置的元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$