41. First Missing Positive

First Missing Positive

題目描述：給定一個未排序的整數陣列 nums，找出其中沒有出現的最小正整數。要求時間複雜度 O(n)，空間複雜度 O(1)（不使用額外空間）。

解題思路：關鍵觀察：對於長度為 n 的陣列，答案一定在 [1, n+1] 範圍內。因為陣列最多包含 n 個不同正整數，所以 1 到 n+1 中至少有一個不存在。

循環排序（Cyclic Sort）法：利用陣列本身作為雜湊表——將數字 v 放到索引 v-1 的位置上。

第一趟：歸位

• 遍歷每個位置 i：若 nums[i] 在範圍 [1, n] 內，且 nums[i] != nums[nums[i]-1]（目標位置上的值不同），就將 nums[i] 與 nums[nums[i]-1] 交換。重複直到無法再交換。

第二趟：掃描

• 遍歷 i 從 0 到 n-1：若 nums[i] != i+1，則 i+1 就是第一個缺失的正整數。
• 若全部正確歸位，答案為 n+1。

時間複雜度：O(n) — 雖然有雙層迴圈（外層 for + 內層 while），但每個元素最多被交換一次（每次交換都讓至少一個元素到達正確位置），所以總交換次數不超過 n 次，整體線性。

空間複雜度：O(1) — 直接在原陣列上原地操作，只用了固定幾個額外變數，不需要任何額外的陣列或雜湊表。

方法一：雜湊集合法（Hash Set） 將所有數字存入 unordered_set，然後從 1 開始逐一查詢是否存在，回傳第一個不存在的正整數。時間複雜度 O(n)，但空間複雜度 O(n)，不符合題目 O(1) 空間的要求。實作最簡單，適合面試時先提出再優化。

方法二：負號標記法（Negative Marking） 先把所有非正整數或超出範圍（>n）的數改為 n+1（哨兵值）。再遍歷陣列，對於每個值 v = |nums[i]|，若 v 在 [1, n] 範圍內，將 nums[v-1] 改為負數（表示 v 存在）。最後掃描找第一個正數的位置 i，回傳 i+1；若全為負數則回傳 n+1。時間複雜度 O(n)，空間複雜度 O(1)，但需要多次遍歷且邏輯較繁雜。

1. 如果允許使用 O(n) 額外空間，有哪些更簡單的解法？與循環排序法相比各有什麼優缺點？
2. 本題答案範圍一定在 [1, n+1] 內，這個觀察是解題的關鍵；如果題目改為「找第 k 個缺失的正整數」，如何高效求解？
3. 循環排序（Cyclic Sort）這個技巧適用於哪類問題的通用模板？請列舉至少兩道可以用相同思路解決的 LeetCode 題目。