First Missing Positive -- LeetCode

這道題要求用線性時間和常量空間，思想借鑒到了Counting sort中的方法，不了解的朋友可以參見Counting sort - Wikipedia。既然不能用額外空間，那就只有利用數組本身，跟Counting sort一樣，利用數組的index來作為數字本身的索引，把正數按照遞增順序依次放到數組中。即讓A[0]=1, A[1]=2, A[2]=3, ... , 這樣一來，最後如果哪個數組元素違反了A[i]=i+1即說明i+1就是我們要求的第一個缺失的正數。對於那些不在范圍內的數字，我們可以直接跳過，比如說負數，0，或者超過數組長度的正數，這些都不會是我們的答案。代碼如下：

public int firstMissingPositive(int[] A) {
    if(A==null || A.length==0)
    {
        return 1;
    }
    for(int i=0;i0 && A[A[i]-1]!=A[i])
        {
            int temp = A[A[i]-1];
            A[A[i]-1] = A[i];
            A[i] = temp;
            i--;
        }
    }
    for(int i=0;i實現中還需要注意一個細節，就是如果當前的數字所對應的下標已經是對應數字了，那麼我們也需要跳過，因為那個位置的數字已經滿足要求了，否則會出現一直來回交換的死循環。這樣一來我們只需要掃描數組兩遍，時間復雜度是O(2*n)=O(n)，而且利用數組本身空間，只需要一個額外變量，所以空間復雜度是O(1)。

這道題個人還是比較喜歡的，既有一點算法思想，在實現中又有一些注意細節，而且整體來說模型比較簡單，很適合在面試中出現。