41 First Missing Positive

https://leetcode.com/problems/first-missing-positive/#/description

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

For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.

Your algorithm should run inO(n) time and uses constant space.

分析及代码

先上代码

public int firstMissingPositive(int[] nums) {
    int len = nums.length;
    for(int i = 0; i < len; i++) {
        while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
            swap(nums, nums[i] - 1, i);
        }
    }
    for(int i = 0; i < len; i++) {
        if(nums[i] != i + 1) {
            return i + 1;
        }
    }
    return len + 1;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

这个方法特别巧，利用index记录信息。基本概念就是，如果数组中有2，我们就把它换到idx = 1的地方，如果3就放到idx = 2的地方，把所有数都放好之后，我们再过一遍数组，第一个idx位对应的值不是idx+1的，就是答案。

这题的重点是找到第一个缺失的正数，所以

1. 如果是负数，我们就无视
2. 如果是大于len的数，我们也无视，比如说待处理数组是[100000, 1]，100000在这并没有什么意义，因为离第一个缺失的数太远了，一个长度为2的待处理的数组，可能缺失的正数，最大的可能也就是3，所以大于3的数，根本没有意义，无视

关于时间复杂度：

首先要知道，时间复杂度是O(n)。一个数字被遇到有两种可能，一种是不在[1, len]的范围直接无视，在这个范围的话，最多会遇到两次，第一次是立即放到它应该在的位置上，第二次是index过一遍路过，这时它已经在正确的位置上了，被跳过了

所以O(2n)，所以也是O(n)