分享一道leetcode上的題，當然，居然不是放在刷題貼里來講，意味著分享的這道題不僅僅是教你怎么來解決，更重要的是這道題引發出來的一些解題技巧或許可以用在其他地方，下面我們來看看這道題的描述。

問題描述

給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。

示例 1:輸入: [1,2,0]
輸出: 3
示例 2:輸入: [3,4,-1,1]
輸出: 2
示例 3:輸入: [7,8,9,11,12]
輸出: 1
復制代碼

說明: 你的算法的時間復雜度應為O(n)，并且只能使用常數級別的空間。

解答

這道題在 leetcode 的定位是困難級別，或許你可以嘗試自己做一下，然后再來看我的解答，下面面我一步步來分析，秒殺的大佬請忽略.....

對于一道題，如果不能第一時間想到最優方案時，我覺得可以先不用那么嚴格，可以先采用暴力的方法求解出來，然后再來一步步優化。像這道題，我想，如果可以你要先用快速排序先把他們排序，然后在再來求解的話，那是相當容易的，不過 O(nlogn) 的時間復雜度太高，其實我們可以先犧牲下我們的空間復雜度，讓保證我們的時間復雜度為 O(n)，之后再來慢慢優化我們的空間復雜度。

方法一：采用集合

我們知道，如果數組的長度為 n，那么我們要找的目標數一定是出于 1~n+1 之間的，我們可以先把我們數組里的所有數映射到集合里，然后我們從 1~n 開始遍歷判斷，看看哪個數是沒有在集合的，如果不存在的話，那么這個數便是我們要找的數了。如果 1~n 都存在，那我們要找的數就是 n+1 了。

不過這里需要注意的是，在把數組里面的數存進集合的時候，對于 小于 1 或者大于 n 的數，我們是不需要存進集合里的，因為他們不會對結果造成影響，這也算是一種優化吧。光說還不行，還得會寫代碼，代碼如下：

    public int firstMissingPositive(int[] nums) {Set<Integer> set = new HashSet<>();int n = nums.length;for (int i = 0; i < n; i++) {if (nums[i] >= 1 && nums[i] <= n) {set.add(nums[i]);}}for (int i = 1; i <= n; i++) {if (!set.contains(i)) {return  i;}}return n + 1;}
復制代碼

采用 bitmap

方法一的空間復雜度在最塊的情況下是 O(n)，不知道大家還記不記得位算法，其實我們是可以利用位算法來繼續優化我們的空間的，如果不知道位算法的可以看我直接寫的一篇文章：

1、什么是bitmap算法。

2、自己用代碼實現bitmap算法;

通過采用位算法，我們我們把空間復雜度減少8倍，即從 O(n) -> O(n/32)，但其實 O(n/32) 任然還算 O(n)，不過，在實際運行的時候，它是確實能夠讓我們運行的更快的，在 Java 中，已經有自帶的支持位算法的類了，即 bitSet，如果你沒學過這個類，我相信你也是能一眼看懂的，代碼如下：

    public int firstMissingPositive2(int[] nums) {BitSet bitSet = new BitSet();int n = nums.length;for (int i = 0; i < n; i++) {if (nums[i] >= 1 && nums[i] <= n) {bitSet.set(nums[i]);}}for (int i = 1; i <= n; i++) {if (!bitSet.get(i)) {return  i;}}return n + 1;}
復制代碼

方法3：最終版本

如果這個數組是有序的，那就好辦了，但是如果我們要把它進行排序的話，又得需要 O(nlogn) 的時間復雜度，那我們有沒有啥辦法把它進行排序，然后時間復雜度又不需要那么高呢？

答是可以，剛才我們說過，對于那些小于 1 或者大于 n 的數，我們是其實是可以不理的，居然我們，我們需要處理的這些數，他們都是處于 1~n 之間的，那要你給這些處于 1~n 之間的數排序，并且重復的元素我們也是可以忽略掉的，記錄一個就可以了，那么你能不能在 O(n) 時間復雜度排序好呢？

不知道大家是否還記得我之間寫過的下標法？

一些常用的算法技巧總結。

或者是否還記得計數排序？（計數排序其實就是下標法的一個應用了）

不過學過計數排序的朋友可能都知道，計數排序是需要我們開一個新的數組的，不過我們這里不需要，這道題我們可以這樣做：例如對于 nums[i]，我們可以把它放到數組下標位 nums[i] - 1 的位置上，這樣子一處理的話，所有 1<=nums[i]<=n 的數，就都是是處于相對有序的位置了。注意，我指的是相對，也就是說對于 1-n 這些數而言，其他 小于 1 或者大于 n 的我們不理的。例如對于這個數組 nums[] = {4, 1, -1, 3, 7}。

讓 nums[i] 放到數組下標為 nums[i-1]的位置，并且對于那些 nums[i]<=0 或 nums > n的數，我們是可以不用理的，所以過程如下：從下標為 0 開始向右遍歷

1、把 4 放在下標為 3 的位置，為了不讓下標為 3 的數丟失，把下標為 3 的數與 4進行交換。

2、此時我們還不能向右移動來處下標為1的數，因為我們當前位置的3還不是處于有序的位置，還得繼續處理，所以把 3 與下標為 2 的數交換

3、當前位置額數為 -1，不理它，前進到下標為 1 的位置，把 1 與下標為 0的數交換

4、當前位置額數為 -1，不理它，前進到下標為 2 的位置，此時的 3 處于有序的位置，不理它繼續前進，4也是處于有序的位置，繼續前進。

5、此時的 7 > n，不理它，繼續前進。

遍歷完成，此時，那些處于 1~n的數都是處于有序的位置了，對于那些小于1或者大于n的，我們忽略它假裝沒看到就是了。

這里還有個要注意的地方，就是 nums[i] 與下標為 nums[i]-1的數如果相等的話也是不需要交換的。

接下來，我們再次從下標 0 到下標 n-1 遍歷這個數組，如果遇到 nums[i] != i + 1 的數，，那么這個時候我們就找到目標數了，即 i + 1。

好吧，我覺得我講的有點啰嗦了，還一步步話題展現過程給你們看，連我自己都感覺有點啰嗦了，大佬勿噴哈。最后代碼如下：

    public int firstMissingPositive(int[] nums) {if(nums == null || nums.length < 1)return 1;int n = nums.length;for(int i = 0; i < n; i++){// 這里還有個要注意的地方，就是 nums[i] 與下標為 nums[i]-1的數如果相等的話// 也是不需要交換的。while(nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i]-1] ){// 和下標為 nums[i] - 1的數進行交換int tmp = nums[i];nums[i] = nums[tmp - 1];nums[tmp - 1] = tmp;}}for(int i = 0; i < n; i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}
復制代碼

這道題我覺得還是由挺多值得學習的地方的，例如它通過這道原地交換的方法，使指定范圍內的數組有序了。

還有就是這種通過數組下標來解決問題的方法也是一種常用的技巧，例如給你一副牌，讓你打亂順序，之后分發給4個人，也是可以采用這種方法的，詳情可以看這道題：什么是洗牌算法。

最后推廣下我的公眾號：苦逼的碼農：公眾號里面已經有100多篇原創文件，也分享了很多實用工具，海量視頻資源、電子書資源，關注自提。點擊掃碼關注哦。 戳我即可關注，