描述問(wèn)題

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

限制：時(shí)間復(fù)雜度為 ，空間復(fù)雜度為 。

示例 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
描述：略

請(qǐng)沒做過(guò)此題的讀者先思考片刻......

分析問(wèn)題

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

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

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

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

第二步：核心問(wèn)題

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

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

否則，。

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

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

第三步：實(shí)現(xiàn)細(xì)節(jié)

遍歷數(shù)組 。

當(dāng)遍歷到某個(gè)索引 時(shí)，可能會(huì)有下述 3 種情況：

該元素?zé)o法在數(shù)組中配位， 或者 。此時(shí)無(wú)需做任何額外處理，只進(jìn)行 i++。

與該元素值相同的某個(gè)元素已是配位元素， 。此時(shí)可能會(huì)有下述兩種情況（無(wú)論哪種情況，同樣只需進(jìn)行 i++）：

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

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

除了上述的其他情況：

需要交換配位

此時(shí)交換 和 的值，其目的是用當(dāng)前 的值給 配位。

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

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

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

我們?cè)俅螐念^開始遍歷數(shù)組 。如果到遇到一個(gè)不配位的元素（nums[i] != i+1），則缺失最小正整數(shù)為 ；如果直到遍歷結(jié)束也沒有不配位元素，則缺失最小正整數(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

復(fù)雜度分析

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

空間復(fù)雜度：由于我們?cè)谠瓟?shù)組 上進(jìn)行操作，因而沒有額外的空間申請(qǐng)。所以該算法的空間復(fù)雜度為 。

總結(jié)

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

審核編輯：湯梓紅