41. First Missing Positive

Flip

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 0 和负数为无效的数字，我们并不关心
            if (nums[i] <= 0) {
                // 设置为我们不会翻转的数字
                nums[i] = nums.length + 1;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            // 将合法的递增的值对应的位置翻转为负数
            int abs = Math.abs(nums[i]);
            if (abs <= nums.length) {
                // nums[i] 是范围内的正整数
                int targetIndex = abs - 1;
                // 兼容单个位置被多次翻转的情况
                nums[targetIndex] = nums[targetIndex] > 0 ? -nums[targetIndex] : nums[targetIndex];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            // 留下的正数说明该位置未被翻转过，对应的索引加 1 即为缺失的正数
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }
}

Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int firstMissingPositive(int[] nums) {
        // idx:    0, 1, 2, 3
        // nums:   1, 2, 3, 4

        // nums = [3, 4, -1, 1]
        //         -1, 4, 3, 1
        //         -1, 1, 3, 4
        //         1, -1, 3, 4

        // 将出现过的正整数 [1, n] 映射至 [0, n - 1], 然后遍历数组，当 nums[i] != i + 1 时即为缺失的首个正整数
        for (int i = 0; i < nums.length; i++) {
            int targetIndex = nums[i] - 1; // Integer.MIN_VALUE - 1 = Integer.MAX_VALUE, 因为本题数组长度不长，所以无需担心越界问题
            while (targetIndex >= 0 && targetIndex < nums.length && nums[i] != nums[targetIndex]) { // 注意交换的前提是值不同，否则 [1, 1] 将陷入死循环
                swap(nums, i, targetIndex);
                targetIndex = nums[i] - 1; // 注意同一个索引可能需要多次交换，终止条件为遇到重复的数字或负数
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

References

41. First Missing Positive