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.

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

题目说清楚了，很简单，但是实现起来还是有些细节比较烦人。首先，不能按照A[i] = i来存，因为题目要求寻找正数，如果A[0]用来存储0的话，会影响数据处理。比如当A = {1}的时候，如果A[0] = 0的话，根本没地方存1的值了。所以正确的存储方式应该是A[i]= i+1.
如果当前数组找不到目标值的话，那么目标值就应该是n+1.这个容易漏了。

 1 public class Solution {
 2     public int firstMissingPositive(int[] A) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         if(A == null || A.length == 0)
 5             return 1;
 6         int len = A.length;
 7         for(int i = 0; i < len; i ++){
 8             while(A[i] != i + 1){
 9                 if(A[i] < 1 || A[i] > len || A[i] == A[A[i] - 1]){// 最后一个说明有重复[ 1, 1 ]
10                     break;
11                 }
12                 else{
13                     int tmp = A[i];
14                     A[i] = A[tmp - 1];
15                     A[tmp - 1] = tmp;
16                 }
17             }
18         }
19         for(int i = 0; i < len; i ++){
20             if(A[i] != i + 1){
21                 return i + 1;
22             }
23         }
24         return len + 1;
25     }
26 }

第二遍：

这个就是桶排序，先确定桶的大小，即max。然后将存在的元素填到桶里去。再遍历一次就可以找出那个数字。

 1 public class Solution {
 2     public int firstMissingPositive(int[] A) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         if(A == null || A.length == 0) return 1;
 5         int max = 0;
 6         for(int i = 0; i < A.length; i ++){
 7             max = max < A[i] ? A[i] : max;
 8         }
 9         boolean[] map = new boolean[max];
10         for(int i = 0; i < A.length; i ++){
11             if(A[i] > 0) map[A[i] - 1] = true;
12         }
13         for(int i = 0; i < map.length; i ++){
14             if(!map[i]) return i + 1;
15         }
16         return map.length + 1;
17     }
18 }

第三遍：

 1 public class Solution {
 2     public int firstMissingPositive(int[] A) {
 3         if(A == null || A.length == 0) return 1;
 4         for(int i = 0; i < A.length; i ++){
 5             while(A[i] != i + 1){
 6                 if(A[i] < 1 || A[i] > A.length || A[i] == A[A[i] - 1]) break;
 7                 int tmp = A[i];
 8                 A[i] = A[tmp - 1];
 9                 A[tmp - 1] = tmp;
10             }
11         }
12         for(int i = 0; i < A.length; i ++)
13             if(A[i] != i + 1) return i + 1;
14         return A.length + 1;
15     }
16 }