[LeetCode] First Missing Positive

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.

解题思路:

这道题非常不错，最直接想到的办法就是（1）排序，然后扫描，或者（2）用一个数组来记录已经出现过的值。但是题目要求时间复杂度为O(n)，空间复杂度为常数，（1）方法时间复杂度为O(nlogn)，（2）方法空间复杂度为O（n），均不符合要求。

一个非常impressive的办法是交换的思想，将值为a的数移动到nums[a-1]下（若a在允许的范围之内）。最后再扫描一遍数组，发现值不等于其下标+1的就是所求。

需要注意的有两点：

（1）可能会有多个相同的值。若两个值相同，则不交换

（2）注意下标是从0开始的，而值是从1开始的。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        for(int i=0; i<len; ){
            if(nums[i]>0 && nums[i]<=len && nums[i]!=i+1 && nums[i]!=nums[nums[i]-1]){
                swap(nums, i, nums[i]-1);
            }else{
                i++;
            }
        }
        for(int i=0; i<len; i++){
            if(i + 1 != nums[i]){
                return i + 1;
            }
        }
        
        return len + 1;
    }
private: 
    void swap(vector<int>& nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

[LeetCode] First Missing Positive

原文：http://blog.csdn.net/kangrydotnet/article/details/45503423