繼續每日一題
今天給大家帶來一道將數組視為哈希表的算法
題目描述：
給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。
題目示例：
由于題目要求我們「只能使用常數級別的空間」，而要找的數一定在 [1, N + 1] 左閉右閉（這里 N 是數組的長度）這個區間里。因此，我們可以就把原始的數組當做哈希表來使用。事實上，哈希表其實本身也是一個數組；
最小正整數從1開始，那么沒有出現的最小正整數一定在1到n+1之間（因為如果1到n都出現了，那么答案就是n+1）
所以我們可以只考慮數組中的1到n之間的數，負數、0和大于n的數可以忽略（因為它們不影響1到n之間的最小缺失正整數）。
考慮到對時間和空間復雜度的要求，我們可以采用原地置換，具體流程通過文字描述不太直觀，下面通過一個case給大家描述一下：
數組 [3,4,-1,1]
-
i=0，nums[0]=3，它應該在位置2（即下標2），交換nums[0]和nums[2]：得到[-1,4,3,1]
然后i=0，此時nums[0]=-1，不在1到4范圍內，跳過。 -
i=1，nums[1]=4，它應該在位置3，交換nums[1]和nums[3]：得到[-1,1,3,4]
然后i=1，此時nums[1]=1，它應該在位置0，但是位置0是-1，交換：得到[1,-1,3,4]
然后i=1，現在nums[1]=-1，跳過。 -
i=2，nums[2]=3，在位置2（正確），跳過。
-
i=3，nums[3]=4，在位置3（正確），跳過。
然后遍歷數組
- i=0，num[0]=1（正確）；
- i=1，num[1]=-1，但實際上i=1，對應的數是2，所以返回i+1
但是在置換過程中可能會存在當前位置和要置換的位置的數值是相同的，導致死循環，所以在置換之前還需要比較兩個值是否相同
核心邏輯如下：
- 當前元素：currentVal=nums[i]
- 當前元素需要在的位置：index=currentVal - 1，因為數組下標從0開始，所以需要減一
- 要置換的元素：nums[index]
while (true) {int currentVal = nums[i];//當前元素需要置換到該位置，數組下標從0開始，所以需要減一int changeIndex = currentVal - 1;int needChangeVal = nums[changeIndex];if (currentVal < 1 || currentVal > n) {//不在有效范圍無需置換break;}int needChangeVal = nums[changeIndex];if (currentVal == needChangeVal) {//兩個數字相等，無需置換break;}nums[i] = needChangeVal;nums[changeIndex] = currentVal;}
完整代碼如下：
public static int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; i++) {while (true) {int currentVal = nums[i];//當前元素需要置換到該位置，數組下標從0開始，所以需要減一int changeIndex = currentVal - 1;if (currentVal < 1 || currentVal > n) {//不在有效范圍無需置換break;}int needChangeVal = nums[changeIndex];if (currentVal == needChangeVal) {//兩個數字相等，無需置換break;}nums[i] = needChangeVal;nums[changeIndex] = currentVal;}}for (int i = 0; i < n; i++) {int currentVal = nums[i];if (currentVal != i + 1) {return i + 1;}}//如果都存在則返回 n+1return n + 1;}
