41. First Missing Positive

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.

My Thought

题目大意

给定一个数组，找出第一个丢失的正数。

关键在于 O(n)的时间复杂度和常数的空间复杂度

算法

不能用一般的排序做了，可以借鉴 计数排序 的思想。

对于目标数组 \(A\) ,有长度 \(A.length\)，如果 \(A\) 是一个完美不丢失的数组，即有:

可以看到这个完美数组有一个性质：

那么对于不完美的数组，我们可以遍历一次，交换元素位置，使该数组的全部元素尽可能在其完美的位置上。这样排完一遍，我们再遍历排序后的数组，如果找到不满足上述性质的位置，就是第一个缺失的正数。

这样交换只用到了一个整数空间，两遍遍历则是2*O(n)

伪代码

PROCEDURE findMissingPositive(int A[])

	for i = 0 to A.length-1 do:

    	if A[i] <= A.length and A[i]>0 and

            		A[A[i]-1]!=A[i]

            change(A[i],A[A[i]-1])

    for i=0 to A.length-1 do:

    	if A[i]!= i+1

        	return i+1

    return A.length+1

Code(C++ 3ms)

class Solution {

public:

    int temp;

    int firstMissingPositive(vector<int>& nums) {

        if(nums.size()==0)

            return 1;

        for(int i=0;i<nums.size();++i){

            if(nums[i]<=nums.size()&&nums[i]>0&&nums[nums[i]-1]!=nums[i]){

                temp = nums[nums[i]-1];

                nums[nums[i]-1]=nums[i];

                nums[i] = temp;

                i--;

            }

        }

        for(int i=0;i<nums.size();++i){

            if(nums[i]!=i+1)

                return i+1;

        }

        return nums.size()+1;

    }

};