算法解題：缺失的最小正整數(shù)

描述問題

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

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

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

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

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

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

分析問題

第一步：有序數(shù)組

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

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

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

第二步：核心問題

繼續(xù)思考我們會發(fā)現(xiàn)一個重要的問題，也是該題目的核心所在，即缺失最小正整數(shù) 的取值范圍是 。

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

否則，。

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

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

第三步：實現(xiàn)細節(jié)

遍歷數(shù)組 。

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

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

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

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

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

除了上述的其他情況：

需要交換配位

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

繼續(xù)處理新的 元素

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

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

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

實現(xiàn)代碼

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 行是計算最密集的（嵌套循環(huán)），其所做的處理是交換兩個元素以進行配位。由于數(shù)組的每個索引最多只會進行一次配位，因此此處代碼最多被執(zhí)行 次。另外還有兩個 次 for 循環(huán)。所以該算法的時間復雜度為 。

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

總結

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

審核編輯：湯梓紅