Description
給定未排序的整數陣列
nums，找出最小的缺失正整數。要求 O(n) 時間和 O(1) 額外空間。
Example:
Input: nums = [3,4,-1,1] Output: 2
Intuition#
核心思路：答案一定在
[1, n+1]範圍內（n 為陣列長度）。利用陣列本身作為 Hash Table，將每個值v放到nums[v-1]的位置，再掃描找第一個nums[i] != i+1的位置。
- 若陣列包含 1 到 n 所有數，答案是 n+1
- 否則答案在 1 到 n 之間
- Cyclic Sort：將每個在
[1, n]範圍內的數交換到正確位置 - 第二次遍歷找第一個位置不對的 index
Approaches#
1: HashSet#
- 概念: 將所有數字放入 HashSet，從 1 開始逐一檢查是否存在
- 時間複雜度:
O(n)- 建 Set + 線性掃描 - 空間複雜度:
O(n)- HashSet（不滿足題目要求的 O(1) 空間）
class Solution {
fun firstMissingPositive(nums: IntArray): Int {
val set = HashSet<Int>()
for (num in nums) set.add(num)
for (i in 1..nums.size) {
if (i !in set) return i
}
return nums.size + 1
}
}⭐2: Cyclic Sort (Index as Hash)#
- 概念: 原地將每個值
nums[i]交換到nums[nums[i]-1]，使值v出現在 indexv-1。然後掃描第一個不符的位置 - 時間複雜度:
O(n)- 每個元素最多被交換一次到正確位置 - 空間複雜度:
O(1)- 原地操作
class Solution {
fun firstMissingPositive(nums: IntArray): Int {
val n = nums.size
// Cyclic Sort：將 nums[i] 放到 nums[nums[i]-1]
for (i in nums.indices) {
while (nums[i] in 1..n && nums[nums[i] - 1] != nums[i]) {
val target = nums[i] - 1
val temp = nums[i]
nums[i] = nums[target]
nums[target] = temp
}
}
// 找第一個 nums[i] != i + 1 的位置
for (i in nums.indices) {
if (nums[i] != i + 1) return i + 1
}
return n + 1
}
}Cyclic Sort 的 while 條件中
nums[nums[i]-1] != nums[i]很重要：它避免了重複值造成的無限迴圈。若目標位置已經有正確的值，就不再交換。
🔑 Takeaways#
- Pattern: 「找缺失的正整數」或「值域為 [1, n]」-> Cyclic Sort / Index as Hash
- 關鍵技巧: 利用陣列 index 本身作為 Hash 函數（值 v 放在 index v-1），實現 O(1) 空間的「Hash Table」。類似題目還有 442 Find All Duplicates 和 448 Find All Numbers Disappeared