41. 缺失的第一個正數

困難

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

請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。

示例 1：

輸入：nums = [1,2,0] 輸出：3

解釋：范圍 [1,2] 中的數字都在數組中。

示例 2：

輸入：nums = [3,4,-1,1] 輸出：2

解釋：1 在數組中，但 2 沒有。
?

示例 3：

輸入：nums = [7,8,9,11,12] 輸出：1

解釋：最小的正數 1 沒有出現。

提示：

1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

思路：直接使用Hash表來記錄下每個數, 預處理后再去檢查1 ~ n + 1 缺失的數.【時間復雜度O(n) 空間復雜度O(n)】 而題目要求空間復雜度O(1)

解決關鍵: 數組本身是有兩個位置可以記錄數據的數據結構，一個是索引下標，另一個就是值. 利用這一點來實現常數級別空間復雜度的解決

這里將每個遍歷到的值都將數組的索引做一個標記 (為了不影響這個數本身的價值,將其標為負數, 用到該數時再取絕對值, 但如果這里原來數組的數本來就是負數呢? 這里是要找缺失的第一個正數,負數是沒有價值的, 所以我們可以將初始就為負數的數替換為一個特定的數. 為了不影響結果, 這個特定的數是要保證是存在的, 所以我們可以將其替換為 1 ~ n+1 的任何數, 只要在預處理的時候檢查他存在, 但題目要求的是需要第一個正數, 故如果選擇后面的數會出現漏掉前面較小的數的檢查. 所以最小數1是你的不二選擇)。 用索引下標表示這個數已經存在, 處理完后只需要找到這個數組的第一個正數, 他的下標就是第一個沒有出現的正數。而缺失的數肯定在1 ~ n+1 之間的。如果都為負數則缺失的就是 n+1

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;// 檢查負數的最小標記是否存在 1boolean std = false;for(int i = 0; i < n; i ++) if(nums[i] == 1) std = true;// 不存在直接返回第一個缺失的正數 1if(!std) return 1;// 預處理,為了不讓初始值為負數的數干擾后序檢查的結果. 將無意義的負數都標記為已經存在的 1for(int i = 0; i < n; i ++) if(nums[i] <= 0) nums[i] = 1;// 將存在的數全都標負, 數組下標是從0開始的, 所以處理時都進行 -1for(int i = 0; i < n; i ++){int t = Math.abs(nums[i]);// 缺失的數只在1 ~ n+1 之間, 超過范圍的其它數不需要處理if(t <= n) nums[t - 1] = -Math.abs(nums[t - 1]);}// 找到第一個正數for(int i = 0; i < n; i ++){// 找到時進行 + 1 恢復if(nums[i] > 0) return i + 1;}return n + 1;}
}