41. First Missing Positive

这道题要求比较奇特，有点费解。
它要求找到第一个missing的正数，从1开始。
所以我们的range肯定在1到N + 1之间， N是输入的size.
所以最简单的办法是，我们新建一个N + 1 的空array helper,
扫描数组，如果遇到一个数是在1到N+1之间，则在helper Array里标记一下这个数出现过。
然后最后找第一个没出现过的数。

但题目要求不能用额外的空间。
这就比较有挑战性。那一个很常见的做法就是reuse input array的空间。
从左往右扫，比如如果第一个数是3,就在index 为（3 - 1） = 2的地方标记一下这个数出现过。但是难点是怎么标记？ 答案给了一个做法我觉得不够自然。
因为我们只关心正数，所以我们可以把用负数表示这个位子上的数出现没出现过。
如果 array[2] = 4, 那我们就把4变成-4， 表示index为2上的数(就是3)出现过。
如果array[2] 本来就是个负数怎么办？ 反正我们也不关心负数，也不关心那些不在1 到 N 之间的数， 那我们就先把这些数都删掉（不是真正删，只是把值改成 0）
这样我们用数的绝对值表示原来的数，数的正负号表示该在这个位子上出现的数有没有出现过。其实就相当于我们把原来的helper array 叠加到input array上。这种奇技淫巧我是非常鄙视的。
如果array[2]是个0, 没有正负号，那我们就把的值等于它本身应该表示的值 * -1。表示它出现了。
这样最后看一遍第一个 >0的位置，用它的index +1就是我们的结果了 。

这个做法应该比官方答案更自然。官方答案 把所有0和负数都预处理成1， 请问你这个1是从哪里冒出来的 。。。要被人给问死。

你去面试的时候回答我这个做法，别人比较不会怀疑你做过这道题。

    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) nums[i] = 0;
            if (nums[i]  > nums.length) nums[i] = 0;
        }
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (n == 0) continue;
            if (n < 0) n *= -1;
            
            if (nums[n - 1] == 0) {
                nums[n - 1] = -1 * (n); // mark appeared.
            } else if (nums[n - 1] > 0){
                nums[n - 1] *= -1; // mark appeared
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) return i + 1;
        }
        return nums.length + 1;
    }