41. First Missing Positive

[Shawngbk]

Q:

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

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

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

寻找数组中第一个未出现的正整数，题目本身比较常见，关键在于题目要求只能使用常数额外空间。

A:

虽然不能再另外开辟非常数级的额外空间，但是可以在输入数组上就地进行swap操作。

思路：交换数组元素，使得数组中第i位存放数值(i+1)。最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程需要遍历两次数组，复杂度为O(n)。

下图以题目中给出的第二个例子为例，讲解操作过程。

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

    for(int j = 0; j < nums.length; j++) {
        if (nums[j] != (j+1))
        return j+1;
    }
    return len + 1;
}
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

}