First Missing Positive

q3256

　　Given an unsorted integer array, find the first missing positive integer.


Example



　　Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
　　分析：
　　我们只需要把1到A.length的数存在原始的数组里，这里有一个要注意的地方就是当我们把一个值放到另一个位置的时候，我们需要把那个值放到它应该在的地方。所以，我们在exchange的时候需要不断自我递归调用exchange method.



1 public class Solution {
2     /**   
3      * @param A: an array of integers
4      * @return: an integer
5      */
6     public int firstMissingPositive(int[] A) {
7         if (A == null || A.length == 0) return 1;
8         
9         for (int i = 0; i < A.length; i++) {
10             if (A <= A.length && A > 0 && A[A - 1] != A) {
11                exchange(A, A);
12             }
13         }
14         
15         for (int i = 0; i < A.length; i++) {
16             if (A != i + 1) {
17                 return i + 1;
18             }   
19         }
20         return A.length + 1;
21     }
22     
23     public void exchange(int[] A, int value) {
24         int temp = A[value - 1];
25         A[value - 1] = value;
26         if (temp <= A.length && temp > 0 && A[temp - 1] != temp) {
27             exchange(A, temp);
28         }
29     }
30 }