引言

在算法面試和數據處理中，尋找缺失的第一個正數是一個經典問題。題目要求給定一個未排序的整數數組，找到其中缺失的最小正整數，且時間復雜度需為O(n)，空間復雜度為O(1)。本文將詳細解析如何通過原地哈希算法高效解決這一問題，并提供完整的Java代碼實現。

---

問題描述

給定一個包含n個整數的數組nums，找出其中沒有出現的最小的正整數。
示例：

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

限制條件：

• 時間復雜度：O(n)
• 空間復雜度：O(1)

---

方法思路：原地哈希算法

傳統方法（如排序或哈希表）無法滿足空間復雜度要求。原地哈希的核心思想是將數值映射到數組索引上，通過交換操作將每個正整數放到其“正確位置”。

算法步驟

1. 處理數組元素

   • 遍歷數組，若當前元素nums[i]是正整數且在[1, n]范圍內，則將其交換到索引nums[i]-1的位置。
   • 使用while循環確保交換后的新元素也被正確處理。

2. 查找缺失值

   • 再次遍歷數組，第一個滿足nums[i] != i+1的位置即為缺失的最小正數。
   • 若所有位置均正確，則缺失值為n+1。

---

完整代碼實現

public class FirstMissingPositive {public int firstMissingPositive(int[] nums) {int n = nums.length;// 原地哈希：將數值x交換到索引x-1的位置for (int i = 0; i < n; i++) {while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums, i, nums[i] - 1);}}// 查找第一個不滿足nums[i] == i+1的位置for (int i = 0; i < n; i++) {if (nums[i] != i + 1) {return i + 1;}}return n + 1;}// 交換數組中的兩個元素private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

---

關鍵代碼解析

1. 原地哈希處理

   while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums, i, nums[i] - 1);
   }
   

   • 條件1：nums[i]必須是有效正整數（1 ≤ x ≤ n）。
   • 條件2：若目標位置的值已正確，則無需交換。
   • 循環處理：交換后，新的nums[i]可能仍需調整，因此使用while而非if。

2. 查找缺失值

   if (nums[i] != i + 1) {return i + 1;
   }
   

   • 第一個不滿足nums[i] == i+1的索引i，其對應的i+1即為缺失值。

---

復雜度分析

• 時間復雜度：O(n)
  每個元素最多被交換一次，兩次遍歷時間復雜度均為O(n)。
• 空間復雜度：O(1)
  僅使用常數級別的額外空間。

---

示例說明

以輸入nums = [3,4,-1,1]為例：

1. 原地哈希處理：
   • 遍歷到3，將其交換到索引2的位置，數組變為[-1,4,3,1]。
   • 遍歷到4，將其交換到索引3的位置，數組變為[-1,1,3,4]。
   • 遍歷到1，將其交換到索引0的位置，數組變為[1,-1,3,4]。
2. 查找缺失值：
   • 索引1的值為-1，不滿足nums[1] == 2，返回2。

---

總結

原地哈希算法通過索引映射和元素交換，將時間復雜度優化至O(n)，空間復雜度優化至O(1)。該方法不僅高效，還能幫助深入理解數組索引與數值之間的關系。掌握這一算法，可輕松應對類似的高頻面試題。