描述問題

問題：給定一個任意無序的整數數組 ，請返回一個在數組中沒有出現的最小正整數。

限制：時間復雜度為 ，空間復雜度為 。

示例 1：
輸入：nums = [3, 1, 2, 4]
輸出：5
描述：1、2、3、4 都在數組中，因此 5 是沒有出現在數組中的最小正整數。

示例 2：
輸入：nums = [-3, 1, 0, 4]
輸出：2
描述：略

示例 3：
輸入：nums = [6, 8, 7, 8]
輸出：1
描述：略

請沒做過此題的讀者先思考片刻......

分析問題

第一步：有序數組

如果要求返回數組中存在的最小正整數，則很容易。僅遍歷一次，并用一個變量記住當前的最小正整數即可。但是題目的要求是返回數組中缺失的最小正整數，這樣我們必須處理無序數組，使其按照某種方式有序才行。如果數組有序，則僅需要最多一次遍歷數組（ 次比較）就能完成任務。

說到數組有序，首先會想到排序算法。處理一般排序的最高效算法就要屬快速排序和歸并排序了。但很遺憾，它們的平均時間復雜度都是 （超出題目的限制）。

還有更高效的排序算法么？當然有啦，正是用于整數的計數排序算法。其時間復雜度正為 。但是，計數排序的空間復雜度要視數組元素（整數）取值范圍而定，而整數的范圍區間已經達到了幾十億。這很顯然不能滿足空間復雜度 的限制。

第二步：核心問題

繼續思考我們會發現一個重要的問題，也是該題目的核心所在，即缺失最小正整數 的取值范圍是 。

如果數組為 [1, 2, 3,..., n-1, n]，則 ，此時值最大。

否則，。

這一步是解決整個問題的最關鍵所在，也就是說我們可以將數組 中的大小在 范圍的元素在長度為 的數組中進行有序排列。而數組 的長度剛好為 ，因此我們就可以不必申請額外空間，僅在原數組上對這些元素進行排序了。

這個排序與計數排序很類似，只不過不需要在對應的位置上記錄相同元素的個數。只需將數組中每個 放到 位置上。我們稱每個滿足 的元素為配位元素。

第三步：實現細節

遍歷數組 。

當遍歷到某個索引 時，可能會有下述 3 種情況：

該元素無法在數組中配位， 或者 。此時無需做任何額外處理，只進行 i++。

與該元素值相同的某個元素已是配位元素， 。此時可能會有下述兩種情況（無論哪種情況，同樣只需進行 i++）：

該元素本身就是配位元素，。

該元素本身是非配位元素，。

除了上述的其他情況：

需要交換配位

此時交換 和 的值，其目的是用當前 的值給 配位。

繼續處理新的 元素

然后，（在 值保持不變的情況下）繼續根據上述 3 種情況處理新的 元素。

直到遍歷結束。對數組 元素的配位已處理完畢。

我們再次從頭開始遍歷數組 。如果到遇到一個不配位的元素（nums[i] != i+1），則缺失最小正整數為 ；如果直到遍歷結束也沒有不配位元素，則缺失最小正整數為 。

實現代碼

deffirstMissingPositive(nums):
n=len(nums)
foriinrange(n):
while1<=?nums[i]?<=?n?and?nums[i]?!=?nums[nums[i]-1]:
????????????nums[nums[i]-1],?nums[i]?=?nums[i],?nums[nums[i]-1]
????for?i?in?range(n):
????????if?nums[i]?!=?i+1:
????????????return?i+1

????return?n+1

復雜度分析

時間復雜度：在 Python 代碼中，看似第 5 行是計算最密集的（嵌套循環），其所做的處理是交換兩個元素以進行配位。由于數組的每個索引最多只會進行一次配位，因此此處代碼最多被執行 次。另外還有兩個 次 for 循環。所以該算法的時間復雜度為 。

空間復雜度：由于我們在原數組 上進行操作，因而沒有額外的空間申請。所以該算法的空間復雜度為 。

總結

雖說本題實現的代碼量并不多，但思考起來卻不算容易。關鍵點就在于要想到使數組有序和缺失最小正整數的范圍。只要明確這兩點，這個問題就會迎刃而解。

審核編輯：湯梓紅