📃 题目描述

题目链接：41. 缺失的第一个正数 (opens new window)

🔔 解题思路

可以马上想到用 HashMap 存 nums，然后从整数 1 开始遍历，第一个在 Map 中找不到的数就是第一个缺失的正整数，但是这种做法的空间复杂度是 O(N)

想要空间复杂度 O(1)，可以用数组来代替哈希表

即下标为 i 存储整数 i + 1（之所以不用下标 i 存储整数 i，是因为这道题目显然不需要 0 这个数）

• 由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组；
• 我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；
• 那么，我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        // corner case
        if (nums == null || nums.length == 0) {
            return 1;
        }

        int i = 0;
        while (i < nums.length) {
            // nums 作为哈希表只能存储 [1, nums.length] 的数
            if (nums[i] <= 0 || nums[i] == i + 1 || nums[i] > nums.length) {
                i ++;
                continue;
            }
            // nums[i] >= 0 && nums[i] != i + 1 && nums[i] <= nums.length
            int index = nums[i] - 1;
            // nums[i] 和 nums[index] 交换
            if (nums[index] != nums[i]) {
                swap(nums, i, index);
            }
            // 如果 nums[i] 已经等于 nums[index] 了，说明存在重复数(比如 [1, 1])，直接 i ++ 就行
            // 不 i++ 的话会陷入死循环
            else {
                i ++;
            }
        }

        for (int j = 0; j < nums.length; j ++) {
            if (nums[j] != j + 1) {
                return j + 1;
            }
        }
        
        // 前面的 N 个元素都找不到的情况下，返回 N + 1
        return nums.length + 1;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：