Problem: 41. 缺失的第一個正數
題目：給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。

【LeetCode 熱題 100】41. 缺失的第一個正數——（解法一）暴力解

整體思路

這段代碼旨在高效地解決 “缺失的第一個正數” 問題。與上一個排序解法不同，此版本采用了一種稱為 “原地哈希” (In-place Hashing) 或 “循環排序” (Cyclic Sort) 的思想，能夠在 O(N) 的時間復雜度和 O(1) 的空間復雜度內完成任務，是此問題的最優解。

算法的核心思想是：嘗試將每個數字 x 放到它“應該”在的位置上。對于一個長度為 n 的數組，如果我們只關心 1 到 n 的正整數，那么數字 1 應該在索引 0 的位置，數字 2 應該在索引 1 的位置，以此類推，數字 x 應該在索引 x-1 的位置。

算法的執行步驟如下：

1. 原地重排數組：

   • 算法通過一個 for 循環遍歷數組。在 for 循環的內部，是一個 while 循環，這是算法的核心。
   • 對于當前位置 i 的數字 nums[i]：
     • while 循環的條件：這個條件非常關鍵，它同時檢查三件事：
       1. nums[i] >= 1 && nums[i] <= n：確保 nums[i] 是一個在 [1, n] 范圍內的有效正數。我們只關心這些數字，任何超出這個范圍的數字（負數、零、或大于 n 的數）都無需處理，因為它們不可能是 1 到 n 范圍內的缺失正數。
       2. nums[i] != nums[nums[i] - 1]：檢查 nums[i] 是否已經在它正確的位置上。nums[i] 應該在的位置是 nums[i] - 1。如果 nums[i] 的值不等于 nums 在 nums[i]-1 索引上的值，說明 nums[i] 還未歸位。
     • 執行交換：如果 while 條件滿足，就執行一次交換，將 nums[i] 與 nums[nums[i] - 1] 的值互換。這個操作的目的就是將 nums[i] 送到它應該在的位置去。
   • 這個 while 循環會持續進行，直到當前 i 位置的數字不再滿足交換條件（可能因為它已經歸位，或者它是一個無效數字）。然后外層 for 循環才會進入下一個 i。

2. 查找缺失的正數：

   • 當第一步的重排完成后，理想情況下，數組 nums 應該形如 [1, 2, 3, ..., n]。
   • 接著，進行第二次遍歷。在這個遍歷中，檢查每個位置 i 的值是否等于 i+1。
   • 如果 nums[i] != i + 1，這意味著 i+1 這個正整數本應在這里，但它不在。由于我們已經把所有能歸位的數字都歸位了，這個不在位置上的 i+1 就是我們找到的第一個缺失的正數。直接返回 i+1。

3. 處理特殊情況：

   • 如果在第二次遍歷中，所有的數字都在它們正確的位置上（即 nums 就是 [1, 2, ..., n]），那么循環會正常結束。
   • 這說明 1 到 n 所有的正數都存在，因此，缺失的第一個正數就是 n+1。

完整代碼

class Solution {/*** 在一個未排序的整數數組中，找到沒有出現的最小的正整數。* 采用原地哈希/循環排序的方法。* @param nums 輸入的整數數組* @return 缺失的最小正整數*/public int firstMissingPositive(int[] nums) {int n = nums.length;// 步驟 1: 原地重排數組，嘗試將每個數字放到它正確的位置上。// 數字 x 應該在索引 x-1 的位置。for (int i = 0; i < n; i++) {// 當 nums[i] 在 [1, n] 范圍內，并且它沒有在正確的位置上時，循環交換。// 正確的位置是指：nums[i] 的值應該等于索引 nums[i]-1 上的值。// 例如，如果 nums[i] = 3，它應該在索引 2 的位置，即 nums[2] 的值應該是 3。while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {// 將 nums[i] 與它目標位置上的數進行交換。int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}// 步驟 2: 查找第一個不滿足 nums[i] == i + 1 的位置。for (int i = 0; i < n; i++) {// 如果在索引 i 上的值不是 i+1，那么 i+1 就是第一個缺失的正數。if (nums[i] != i + 1) {return i + 1;}}// 步驟 3: 如果 1 到 n 都存在，那么缺失的第一個正數就是 n+1。return n + 1;}
}

時空復雜度

時間復雜度：O(N)

1. for 和 while 循環：雖然代碼中有一個嵌套的 while 循環，但它的總執行次數并不是 O(N^2)。
2. 均攤分析：
   • 關鍵在于，每一次 while 循環中的成功交換，都會將至少一個數字（即 nums[nums[i] - 1] 被換過來的那個）放到了它最終正確的位置上。
   • 一個數字一旦被放到正確的位置，它就不會再參與后續的交換了（因為 nums[i] == nums[nums[i] - 1] 條件會使其不滿足 while 循環）。
   • 由于數組中只有 N 個位置，最多只會發生 N 次成功的交換。
   • 因此，所有 while 循環的總執行次數（包括成功的交換和不成功的檢查）加起來是 O(N) 級別的。外層 for 循環也執行 N 次。所以這部分的復雜度是 O(N)。
3. 第二次遍歷：最后的 for 循環遍歷數組一次，時間復雜度為 O(N)。

綜合分析：
算法的總時間復雜度是 O(N) + O(N) = O(N)。

空間復雜度：O(1)

1. 主要存儲開銷：該算法直接在輸入數組 nums 上進行修改，沒有創建任何與輸入規模 N 成比例的新的數據結構。
2. 輔助變量：只使用了 n, i, temp 等幾個常數級別的整型變量。

綜合分析：
算法所需的額外輔助空間是常數級別的。因此，其空間復雜度為 O(1)。這是該問題最優的空間效率。

參考靈神