LeetCode 41. First Missing Positive

[Woodyiiiiiii]

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

---

这道题是找到缺失的最小正数。

我一开始就直接迭代寻找所有正数：

class Solution {
    public int firstMissingPositive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int smallNum = Integer.MAX_VALUE;
        for (int num : nums) {
            set.add(num);
            if (num > 0 && num < smallNum)
                smallNum = num;
        }
        int i = 1;
        for (; i < smallNum; ++i) {
            if (!set.contains(i))
                return i;
        }
        for (i = smallNum + 1; i < Integer.MAX_VALUE;++i) {
            if (!set.contains(i))
                return i;
        }
        return -1;
    }
}

当然，仔细检查题目思考后，发现所寻找的最小正数跟数组元素及长度有关，或者说数组内元素要跟下标匹配才不会缺失，比如说数组[1, 2, 3]对应下标0，1，2，我们就可以知道缺失的正数是数组长度加一了，如果不匹配，比如[2, 1, 4]，也能清楚答案是3。

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        int i;
        boolean[] v = new boolean[nums.length + 1];
        for (i = 0; i < nums.length; ++i) {
            if (nums[i] > 0 && nums[i] <= nums.length) {
                v[nums[i]] = true;
            }
        }
        for (i = 1; i <= nums.length; ++i) {
            if (!v[i]) {
                return i;
            }
        }
        return nums.length + 1;
    }
}

上述做法的时间复杂度是O(n)，空间复杂度是O(n)，但我们离题意核心理念更进一步了。那么难点在于如何继续简化，将空间复杂度缩减至O(1)呢？那么只能在原数组上进行元素的交换。如果在1~n(n是数组长度)内的数字，就交换至合适的位置，否则继续迭代数组元素。为了避免因数字重复进行的无限循环交换，我们需要判断交换后的元素是否与交换前的元素相同，如果相同继续遍历，比如数组[1, 1]的情况，避免进入死循环。

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        int i;
        for (i = 0; i < nums.length; ) {
            if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length) {
                ++i;
                continue;
            }
            int tmp = nums[i];
            swap(nums, i, nums[i] - 1);
            if (nums[i] == tmp) {
                ++i;
            }
        }
        for (i = 0; i < nums.length; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    void swap(int[] nums, int i, int j) {
        if (nums[i] != nums[j]) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }
}

---

参考资料：

• https://leetcode.com/problems/first-missing-positive/
• https://leetcode.com/problems/first-missing-positive/discuss/735695/Java-Time-O(n)-Constant-space-SWAP-approach
• [LeetCode] 41. First Missing Positive grandyang/leetcode#41