數組特性的妙用！如何找到「缺失的第一個正數」
- 2019 年 10 月 6 日
- 筆記
作者 | P.yh
今天分享的題目來源於 LeetCode 第 41 號問題：缺失的第一個正數。題目難度為 Hard。本文使用了一個比較 Trick 的解法。
題目描述
給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。
示例 1:
輸入: [1,2,0] 輸出: 3
示例 2:
輸入: [3,4,-1,1] 輸出: 2
示例 3:
輸入: [7,8,9,11,12] 輸出: 1
說明:
你的演算法的時間複雜度應為O(n)，並且只能使用常數級別的空間。
題目解析
給一個整形數組，找出最小缺失的正整數，例如 [0,-1,2] 中最小缺失的正整數就是 1，[ 1，2 ，4 ，9 ] 中最小缺失的正整數就是 3。
這道題如果不加上 O(n) 時間和 O(1) 空間這樣的限定條件，應該再簡單不過，但是加上了這兩個要求，一下子使問題變得棘手。
怎麼思考呢？
首先這道題給定的條件很有限，輸入參數就 只有數組 ，如果非要用 O(n) 時間和 O(1) 空間來做的話，表示我們除了輸入數組以外，不能藉助任何其他的數據結構。
數組應該是屬於一類最最基礎的數據結構，除去 length 之外，就只有兩個屬性 index 和 value，那這道題就變成了 如何利用數組的 value 和 index 之間的關係來找到最小缺失正整數 ，如果想到了這一點，就已經成功了一半。
如果繼續想下去有幾點是可以明確的：
- 缺失的正整數肯定在 [1, array.length + 1] 這個範圍內
- 我們可以交換輸入數組中的元素的位置來讓 index 和 value 的關係更加明確
- 保證 index 和 value 的關係後，我們可以通過 index 來判定整數的存在性
第一點很好理解，一個數組總共有 array.length 這麼多個數，全部排滿，也就是 1,2,…array.length， 那麼答案就是 array.length + 1，沒有排滿，那麼在這之間肯定是有缺失元素的。
第二點是說我們可以通過交換來讓 index 和 value 形成對應，我們看的是 value，但是 index 可以輔助我們尋找。
前兩點明確了，第三點就是從頭到尾尋找答案的過程。
程式碼實現
public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) { return 1; } for (int i = 0; i < nums.length;) { if (nums[i] <= 0 || nums[i] > nums.length || nums[nums[i] - 1] == nums[i]) { i++; continue; } // swap int tmp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = tmp; } for (int i = 0; i < nums.length; ++i) { if (nums[i] != i + 1) { return i + 1; } } return nums.length + 1; } 總結
程式碼中 index 和 value 的對應關係是 index = value - 1，程式碼實現有兩點需要注意。
- 第一點，交換完後，需要判斷交換過來的數是否需要被放到相應的地方，例如
[2,3,1] - 第二點，元素越界的話，以及元素 value 已經和 index 對應上了，那麼就應該繼續遍歷，例如
[0,-1,1]和[1,1]。
總的來說這道題並沒有涉及什麼演算法和數據結構的應用，有點像腦筋急轉彎的感覺，想到了就做的出，想不到的話就做不出，但是它給我們解數組問題提供了一個新的方向：利用 index 和 value 的對應關係來輔助求解。