41. First Missing Positive

Flip

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

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 将出现过的正整数 [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]) {
                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;
    }
}

Reference

41. First Missing Positive