今天是LeetCode題解系列第21篇，今天來看一道人狠話不多的題目。
題面
題目非常簡單，只有一句話，給定一個整數數組，要求返回最小的不在數組當中的正整數。
看起來有些拗口，簡單解釋一下。我們都知道正整數就是從1開始的整數，所以這道題就是從1開始找到第一個不在數組當中的元素。我們來看下樣例：
樣例 1:
<code>Input: [1,2,0]
Output: 3
/<code>
樣例 2:
<code>Input: [3,4,-1,1]
Output: 2
/<code>
樣例 3:
<code>Input: [7,8,9,11,12]
Output: 1
/<code>
注意:
算法的時間複雜度必須是O(n)，並且只能使用O(1)的存儲空間。
分析
在注意出來之前，我們可能覺得這道題也不是那麼難，很容易就想到解法，但是有了這兩條限制之後就沒那麼簡單了。我們遍歷數組就需要O(n)的複雜度了，怎麼還能找出最小未出現的元素呢？而且還不能申請額外的數組，只能用常數級的存儲，顯然各種輔助數組和容器是不能用了。
我們直接這麼苦苦思索是很難想出解法的，不如來循序漸進 。
我們先來假設沒有這些限制條件的話應該用什麼方法，最容易想到的應該是排序。我們將數組排序，一旦數組有序了之後就方便了。我們從小到大遍歷，很容易就確定哪些元素出現過哪些元素沒有。那麼想要找出來不在數組當中的最小自然數自然也是輕而易舉。分析一下排序我們可以發現，在此過程當中我們並沒有用到額外的空間，唯一不滿足條件的只有我們的時間複雜度是 O(nlogn) 而不是O(n)。
我們寫下代碼：
那我們反過來，如果保證空間可以隨意使用，但是對時間複雜度進行限制，我們能想到什麼辦法呢？
應該也很容易想出來，就是引入額外的容器。比如hashset。hashset的增刪改查的複雜度都可以近似看成是常數級。我們只需要遍歷一次數組，將所有元素插入hashset當中，同時記錄下元素的最大最小值，最後遍歷一下最小值和最大值這個區間，找出不在hashset當中最小的元素即可。n個元素的數組我們可以很容易證明，我們一定可以在n次查找以內找到不在數組當中的自然數。
這段代碼也不難寫：
in-place
上面的兩種做法一種進行了高複雜度的排序，另一種則用到了額外的存儲。看起來這是一個兩難問題，我們不想排序就需要用到存儲，如果不想用存儲呢，那麼則需要元素有序。我們仔細分析一下這兩種情況，就可以找到問題的癥結了，我們有沒有什麼辦法可以兩全其美，既不用額外的存儲又可以保證元素的有序呢？如果我們可以找到一種方法，那麼這個問題就解決了。
這也是我們解題的時候的一個常規的套路，就是對於一些題目而言有一些算法是比較明顯的，但是可能因為這樣或那樣的限制使得並不能應用在當前的問題當中。但是沒關係，我們一樣可以往這方面去想，先找到一個不那麼合適的解法，在此基礎上謀求突破，很多時候要比憑空想出一個完美的方法來容易許多。
那麼我們怎麼突破呢？
還要從題目的要求入手，題目當中規定只能使用常數的存儲空間，意味著我們不能額外開闢數組或者其他容器來存儲數據。有經驗的同學可能已經反映過來了，這是in-place的套路。
in-place並不是一個算法，而是一種思想。它出現的原因也非常簡單，因為我們申請數組等容器的時候需要通過操作系統向內存申請連續的內存，這會涉及到一系列內存管理算法的執行，所以是需要消耗大量時間的。所以在一些高性能的場景下，我們會希望儘量避免空間申請操作。
比如我們想要對數組進行排序，我們直接調用sorted方法的時候，其實在函數內部對數組進行了拷貝，最後返回的其實是拷貝數組排序之後的結果。也就是說我們
獲得的是一個新的數組，只是其中的元素和原來一模一樣。而如果是in-place的方法，我們則不會另外創建數組，而在原數組上進行修改。非in-place的接口不會修改原值，這方便我們追蹤數據的變化，以及撤銷操作。比如Python機器學習領域的大量numpy和pandas的接口默認都不是in-place的，就是這個原因。而in-place的則相反，由於它會直接修改原值，所以如果我們一旦執行錯了，無法撤銷，原數據就找不回了。比如我們排序錯了，明明要降序，不小心排成了升序，一旦執行就無法還原了。但是和非in-place相比，它的耗時更少，也更節約內存。
這題其實已經暗示得很明顯了，我們需要存儲數據，但是又不讓我們申請空間，於是我們只有in-place一條路可以走了。
我們需要設計一個in-place的算法，讓我們可以判斷元素的存在性。再加上題目中的限制是正整數，而且我們要找的是第一個沒有出現的正整數。如果數組的長度是n，那麼其實我們可以鎖定，
答案一定在[1, n+1]之間。原因也很簡單，因為最理想的情況是這個數組當中的n個元素剛好是1到n，這樣我們從1開始遍歷，一直找到n就能得到答案是n+1。否則的話，我們一定可以在遍歷到n+1之前就找到答案，所以綜合一下，答案一定在[1, n+1]之間。如果我們能把這個區間寫出來，其實解法已經就在我們眼前了。既然答案在區間[1, n+1]中間，我們又需要設計一個in-place的方法，那麼我們可以很正常地想到，我們可以將數字放到對應的下標當中去。1放到下標1當中，0放到0當中。
比如[3, 1, 0, 5]，我們拿到第一個元素是3，我們把它放到它應該在的位置，也就是5的位置下去，這個時候我們再來放5，由於5超過了數組的長度，所以進行丟棄。我們往下重複如上的過程，到最後的時候，我們得到的數據情況如下：[0, 1, 5, 3]，我們遍歷一下數組，發現和下標不匹配的位置就是5，它應該對應的數據是2，所以2就是答案。
我一開始是先想到的算法，幾乎是憑空想出來的，沒有前後推導的過程，覺得非常驚豔，有種天馬行空的感覺。後來關聯上的in-place思想之後，才發現隱藏的思路其實非常合情合理。思路有了，代碼真的很簡單：
最後，我們來分析一下這個算法的複雜度，為什麼我們在一重循環當中還套了一個while循環，但是它仍然是O(n)的算法呢？
這個問題我們之前在介紹two pointers和尺取法的時候就曾經介紹過，我們在分析複雜度的時候不能只簡單地看有幾重循環，我們需要細緻地分析。我們要忽略循環，回到問題的本質。我們用循環的本質是為了能夠讓每個元素放到對應的位置，一共需要安排的元素數量是固定的是n個，位置也是固定的是n個，一個元素只有一個位置。那麼我們一次交換至少可以讓一個元素放到正確的位置，那麼問題來了，我們想要把所有元素放置好，需要循環多少次？
我這樣問，大家應該很清楚，一次最少放一個，一共n個，顯然最多放n次。那我們再看while循環當中，每執行一次，不就是放好了一個元素嗎？外圍的循環只是用來枚舉元素的，並不會引入額外的計算，所以這當然是一個O(n)的算法。
最後，今天的題目官方標的難度是Hard，題目本身不難，由於加上了很多限制才提升了難度。今天的題目沒有用到新的算法，純粹是對思維和邏輯的考驗。也因此，我覺得它是一道非常純粹的題，純粹在於它並用不到新的算法，也用不到新的數據結構，就是考察我們分析問題和思考問題的能力。而許多問題則針對性很強，如果之前沒有學過對應的算法則無法做得出來，所以從這點上來說這題
更加公平，非常適合面試。我已經進行了預約，以後如果有面試機會，我可能會問候選人這個問題。今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
