LeetCode 41. First Missing Positive

这个题目虽然是Hard，但是只要想到解法之后，就很简单了。

题目要求：找到最小的、没有出现在数组中的整数，数组未排序。

初看起来，这个至少得排个序才能搞定。但是题目说了，时间复杂度O(n)，空间复杂度O(1)。

如果能把数字n填写到第n-1个，那不就能在O(n)时间内看出来缺失数字了吗？把数字n填写到第n-1个，完全就是遍历一遍所有的数字就可以了啊。

思路就这样出来了：

1. 遍历所有数字，将数字n放到第n-1个位
2. 遍历数组，第一个不满足nums[i]!=i+1的i+1即为缺失的数字

代码如下：

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length;) {
            if (nums[i] > 0 && nums[i] <= nums.length) {
                if (nums[nums[i] - 1] == nums[i]) {
                    // 两者相等就没有必要交换了，next
                    i++;
                    continue;
                }
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
                // 交换完成之后，我们并不能确保当前的nums[i]在该在的位置上了
                // 所以不能贸然处理下一个
                // 这是一个坑
            }
            if (nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1) {
                // 要么这个数字不在0-n内，要么这个数字已经在该在的位置上了
                // 总而言之，next
                i++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                // 所有在范围内的数字都已经到对应位置了
                // 但这个位置没有对应的数字，所以这个数字是缺失了的
                return i + 1;
            }
        }
        // 从0-n都有，所以缺失了n+1
        return nums.length + 1;
    }
}

第一个for循环，虽然i并不一定在每次循环的时候递增，但是总的时间复杂度还是O(n)：

对于所有的数字，要不交换到对应位置，要么不交换：即O(n)。