通过前后交换查找重复的数字

即判断A[i]是否等于i
**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.
代码如下：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        if(n==0)
          return 1;
        
        for(int i=0;i<n;i++)
        { 
           if(nums[i]>0&&nums[i]<n) //要把1,2,3… 放在最前面，这样有利于后续的判断
           {
               if(nums[i]-1==i)
                 continue;
               else if(nums[nums[i]-1]!=nums[i])
               {
                   int temp = nums[nums[i]-1];
                   nums[nums[i]-1] = nums[i];
                   nums[i] = temp;
                   i--;
               }
           }
        }
        for(int i=0;i<n;i++)
        {   
            if(nums[i]!=i+1)
              return i+1;
        }
        return n+1;
    }
};