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

整體思路

這段代碼旨在解決一個經典的數組問題：缺失的第一個正數 (First Missing Positive)。問題要求在一個未排序的整數數組中，找到沒有出現的最小的正整數。例如，在 [3, 4, -1, 1] 中，最小的缺失正數是 2。

該算法采用了一種簡單直觀的 “排序后線性掃描” 的策略。其核心邏輯步驟如下：

1. 排序：

   • 算法的第一步是對整個輸入數組 nums 進行升序排序。
   • 目的：排序是這個解法的關鍵前提。它將所有負數、零和重復的正數都組織起來，更重要的是，它使得我們可以按順序查找 1, 2, 3, ...。一旦排好序，如果這些正整數存在，它們必然會以（可能不連續的）升序出現。

2. 線性掃描與目標追蹤：

   • 算法使用一個變量 ans，初始化為 1。這個 ans 變量可以被看作是“我們正在尋找的目標正整數”。
   • 接著，通過一個 for 循環遍歷排序后的數組。
   • 在循環中，將數組中的當前元素 nums[i] 與我們的目標 ans 進行比較。
     • 如果 nums[i] == ans：這意味著我們找到了當前的目標 1（或 2, 3, …）。因此，我們需要更新我們的目標為下一個正整數，即執行 ans++。
     • 如果 nums[i] != ans：這可能是因為 nums[i] 是一個負數、零、或者是一個比 ans 更大的正數，也可能是重復的數字。在任何這些情況下，我們都還沒有找到當前的目標 ans，所以我們保持 ans 不變，繼續向后查找。

3. 返回結果：

   • 當遍歷完整個數組后，ans 的值就是最小的、沒有在數組中找到的那個正整數。例如，如果數組中有 1 和 2，ans 會被更新到 3。如果在后續的遍歷中沒有找到 3，那么 ans 最終就會停在 3，這正是我們想要的結果。

總而言之，這是一個邏輯簡單、易于理解但時間效率不是最優的解法，因為其性能瓶頸在于排序步驟。

完整代碼

class Solution {/*** 在一個未排序的整數數組中，找到沒有出現的最小的正整數。* @param nums 輸入的整數數組* @return 缺失的最小正整數*/public int firstMissingPositive(int[] nums) {// ans: 我們的“目標”或“候選”的最小缺失正整數，從 1 開始尋找。int ans = 1;// 步驟 1: 對數組進行升序排序。// 這使得我們可以按順序查找 1, 2, 3, ...Arrays.sort(nums);// 步驟 2: 線性掃描排序后的數組for (int i = 0; i < nums.length; i++) {// 如果在數組中找到了我們當前的目標 (ans)，// 說明 ans 不是缺失的，我們需要尋找下一個正整數。if (nums[i] == ans) {// 更新目標為下一個正整數ans++;}}// 遍歷結束后，ans 的值就是第一個沒有在數組中匹配到的正整數。return ans;}
}

時空復雜度

時間復雜度：O(N log N)

1. 排序：Arrays.sort(nums) 是算法中時間開銷最大的部分。在Java中，對基本類型數組的排序采用的是雙軸快速排序（Dual-Pivot Quicksort），其平均時間復雜度為 O(N log N)。
2. 線性掃描：for 循環遍歷整個數組一次，執行 N 次迭代。循環體內部的操作（比較和可能的自增）都是 O(1) 的。因此，這部分的時間復雜度是 O(N)。

綜合分析：
算法的總時間復雜度由排序和線性掃描兩部分構成，即 O(N log N) + O(N)。在 Big O 表示法中，我們只保留最高階項，因此最終的時間復雜度由排序決定，為 O(N log N)。

空間復雜度：O(log N)

1. 主要存儲開銷：該算法在原地修改數組（通過排序），并沒有創建與輸入規模 N 成比例的新的數據結構。
2. 排序的額外空間：
   • Java 的 Arrays.sort 實現（雙軸快速排序）是一種原地排序算法，但它需要遞歸。遞歸調用會占用調用棧（call stack）的空間。
   • 對于一個性能良好的快速排序實現，遞歸棧的深度在平均情況下是 O(log N)，在最壞情況下可能達到 O(N)。
3. 其他變量：ans 和 i 等變量只占用常數級別的空間，即 O(1)。

綜合分析：
算法所需的額外輔助空間主要由排序算法的遞歸調用棧決定。因此，在平均情況下，其空間復雜度為 O(log N)。如果忽略排序算法內部的棧空間，可以認為是 O(1)，但 O(log N) 是一個更精確的分析。

LeetCode 熱題 100】41. 缺失的第一個正數——（解法二）原地哈希