LeetCode --- 41. First Missing Positive

LeetCode --- 41. 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.

這道題的要求是找到數組A（未排序）中第一個缺少的正整數。要求O(n)時間復雜度。

這道題的直接思路就是先排序，然後遍歷一遍就能找到第一個缺少的正整數了。不過這樣的話，時間復雜度是O(nlogn)。

題目要求O(n)時間復雜度，那麼還能不能更快些呢？可以考慮從排序上動手腳。類似於計數排序的思路，申請個同樣大小的空數組B，然後給定數組A，把A中出現的數字放到B中對應於B下標的位置（如果該數字大小超過B的范圍，則不處理），例如把5放到B[4]裡等等。最後，再遍歷B數組，就能找到第一個缺少的正整數了。

由於上面申請的B數組和A一樣大，那麼可不可以直接用A來代替B呢？當然可以，就是在遍歷A的時候，如果數字和位置不對應，就交換到對應位置即可。

時間復雜度：O(n)

空間復雜度：O(1)

 1 class Solution
 2 {
 3 public:
 4     int firstMissingPositive(int A[], int n)
 5     {
 6         for(int i = 0; i < n; ++ i)
 7             while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
 8                 swap(A[i], A[A[i] - 1]);
 9         
10         for(int i = 0; i < n; ++ i)
11             if(A[i] != i + 1)
12                 return i + 1;
13         
14         return n + 1;
15     }
16 };