LeetCode 41. First Missing Positive

Problem

LeetCode 41. First Missing Positive

1. 题目简述

给出一个未排序的整形数组，找出最小的缺失的正整数，要求只能使用常数级别的extra space。例如：

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

2. 算法思路

相关问题：

1. LeetCode 268. Missing Number

Array

这道题是属于比较smart的那种题，比较考验数学思维，做过基本上就会，没做过很难想。属于hard里难度较低的那种。

首先我们对于一个长度为n的数组，它的第一个missing number最大只可能是n+1，边界情况是n个数是由(1…n)不重复组成。

因此，对于负数，0或者大于n的数字，我们都可以把它转化成一个固定的数，这里我们设置为n+1，这样我们就能保证数组中的数都是正整数了。

现在问题在于如何使用常数级别的extra space。我们知道一共是有n个数，数组中的数字经过转化以后都变为了[1, n + 1]之间，因此，如果某个数字i有出现过，我们将第i个数（index为i - 1）置为负数即可（i != n + 1），最后判断第一个出现的正数，那么该index + 1即为所求；如果没有找到正数，那么返回n + 1。

这里有一些小tips需要注意，例如不要对一个数字两次取反，以及计算index的时候需要取绝对值，因为有可能在处理前面的数字的时候把后面的数已经置为负数了。

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 直接看解法的一道题。首先，我们假设n为nums的长度，而最终的答案最多只可能是n+1，也就是说前n个数恰好是1到n。因此我们要先排除负数和0和大于n的数，我们将其都设为n+1。修改以后，数组里每个数字的范围就是1到n+1,然后我们遍历数组，用一个negative的符号来表示当前数字已经出现过了并跳过数字n+1,修改下标的符号。然后遍历数组，如果找到第一个非负数，那么返回它。如果没有找到，返回n+1.
        int n = nums.length;

        // 将不合法的数都变成n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 遍历数组，目前数组中每个数都是在1到n+1之间，将以nums[i]的存在的数为下标的数字变为负数。
        for (int i = 0; i < n; i++) {
            // 防止nums[i]在遍历到的时候已经是负号了
            int num = Math.abs(nums[i]);
            // 防止加两次负号
            if (num <= n && nums[num - 1] > 0) {
                nums[num - 1] = -1 * nums[num - 1];
            }
        }

        // 遍历数组，找到第一个非负数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果没有找到，直接返回n+1
        return n + 1;
    }
}