未排序數組，O(N)時間，常數空間，這道題讓我非常清晰的感覺到算法的魅力。
先想一下如果允許用額外空間的話，我們會怎麼做，對，我們會建立一個hash表，然後從頭到尾的掃描數組，等等，怎麼映射呢？有n個數，要找第一個消失的正正整數，那麼這個消失的正整數的取值范圍是什麼呢？[1, n+1]，之所以包含n+1是因為如果這n數正好是連續的前n個自然數。那我們就知道了，開一個長為n的哈希表，如果當前掃到得數是[1,n]之間的話，就放到數值減1的位置上，如果不是的話就跳過，然後從頭掃一遍這個哈希表，第一個沒被填上的位置加1的那個數，就是第一個消失的數。
難就難在常數空間上，那題目沒有指明不能修改原來的數組，我們能不能就地做一個hash呢？這個要保證個條件，原來位置上的數據不能輕易覆蓋，因為如果像開hash表那樣直接在對應位置上填數據的話，要麼覆蓋，要麼置換，覆蓋會出錯，置換會提高整個算法的復雜度。聰明的你可能已經想到了，我們其實不需要在對應的位置上填上那個數，只要保證能區分出一個數在不在他對應的位置上，因此只要正負就可以了。
原來的負數怎麼處理？負數肯定不符合要求，只要讓他們變成正的，又不會影響我們的結果就好，統一變成n+2是不錯的選擇。現在，數組中的所有數據都是正的了，如果遇到一個大於等於n+1的數，可以直接略過，他們要麼是負數變來的，要麼一開始就太大，不是我們考慮的范圍。如果遇到一個小於n+1的數據，我們可以知道他應該在的位置（A[i]-1），只要把這個位置標記為負的，就可以知道這個數呆在了它應該的位置上了。發現我們並沒有改變原來那個位置上數的數值，它可以繼續發揮作用。只不過每次判斷的時候要加個abs而已。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for(int i=0;i0)
return i+1;
}
return n+1;
}
}; 
