Description
給定長度為
n的陣列nums，其中每個元素在[1, n]範圍內。回傳所有在[1, n]中但未出現在nums中的數字。要求 O(n) 時間且不使用額外空間（輸出不計）。
Example:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]
Intuition#
核心思路：利用陣列本身作為 Hash Table——將出現過的數字對應位置標記為負數，最後正數位置就是缺失的數字。
- 數字範圍是
[1, n]，恰好對應陣列索引[0, n-1] - 遍歷陣列，對每個值
|nums[i]|，將nums[|nums[i]| - 1]設為負數 - 第二次遍歷，正數位置的索引
+ 1就是缺失的數字
Approaches#
1: HashSet#
- 概念: 將所有元素放入 HashSet，遍歷
1..n找不在 Set 中的 - 時間複雜度:
O(n) - 空間複雜度:
O(n)- HashSet
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val set = nums.toHashSet()
val result = mutableListOf<Int>()
for (i in 1..nums.size) {
if (i !in set) result.add(i)
}
return result
}
}⭐2: 原地標記（Negation）#
- 概念: 用元素值當索引，將對應位置標記為負數，最後找出仍為正數的位置
- 時間複雜度:
O(n)- 兩次遍歷 - 空間複雜度:
O(1)- 原地修改（不計輸出）
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
// 標記出現過的數字
for (num in nums) {
val idx = Math.abs(num) - 1
if (nums[idx] > 0) {
nums[idx] = -nums[idx]
}
}
// 收集未被標記的位置
val result = mutableListOf<Int>()
for (i in nums.indices) {
if (nums[i] > 0) {
result.add(i + 1)
}
}
return result
}
}補充：Cyclic Sort
將每個數字放到正確位置（nums[i] 應該在索引 nums[i]-1），最後不在正確位置的就是缺失的。
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
var i = 0
while (i < nums.size) {
val correct = nums[i] - 1
if (nums[i] != nums[correct]) {
nums[i] = nums[correct].also { nums[correct] = nums[i] }
} else {
i++
}
}
val result = mutableListOf<Int>()
for (j in nums.indices) {
if (nums[j] != j + 1) result.add(j + 1)
}
return result
}
}🔑 Takeaways#
- Pattern: 當數字範圍在
[1, n]且陣列長度為n時，可以用「原地標記」或「Cyclic Sort」達到 O(1) 額外空間 - 關鍵技巧: 取絕對值避免重複標記導致錯誤；此模式適用於 LC 442（找重複）、LC 41（找缺失正整數）等題