[LeetCode] 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.

» Solve this problem

[解题思路]
其实就是桶排序，只不过不许用额外空间。所以，每次当A[i]!= i的时候，将A[i]与A[A[i]]交换，直到无法交换位置。终止条件是 A[i]== A[A[i]]。
然后i -> 0 到n走一遍就好了。

[Code]

1:   int firstMissingPositive(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int i =0;  
5:      for(int i =0; i< n; i++)  
6:      {  
7:        while(A[i] != i+1)  
8:        {        
9:          if(A[i] <= 0 || A[i] >n || A[i] == A[A[i] -1]) break;  
10:          int temp = A[i];  
11:          A[i] = A[temp-1];  
12:          A[temp-1] = temp;          
13:        }  
14:      }  
15:      for(int i =0; i< n; i++)  
16:       if(A[i]!=i+1)  
17:        return i+1;  
18:      return n+1;  
19:    }  

[注意]
题目说清楚了，很简单，但是实现起来还是有些细节比较烦人。首先，不能按照A[i] = i来存，因为题目要求寻找正数，如果A[0]用来存储0的话，会影响数据处理。比如当A = {1}的时候，如果A[0] = 0的话，根本没地方存1的值了。所以正确的存储方式应该是A[i]= i+1.
但是由此带来的是，Line 7, 9, 11, 12, 16, 17都需要更改，以反映出这种映射。
还有一点容易遗忘的就是Line18，如果当前数组找不到目标值的话，那么目标值就应该是n+1.这个容易漏了。