題目描述:給定一個已排序的整數陣列 nums,要求就地(in-place)移除多餘的重複項,使每個元素最多出現兩次,並返回新的有效長度 k。前 k 個元素必須依序包含符合條件的結果,其餘位置的值不重要。
解題思路:使用寫入指標 k 追蹤下一個寫入位置。對陣列中的每個元素 nums[i],判斷是否需要寫入:若 k < 2(前兩個元素必定保留),或者 nums[i] != nums[k-2](當前元素與已寫入區間的倒數第二個元素不同,表示尚未出現兩次),則將 nums[i] 寫入 nums[k] 並將 k 加一。由於陣列已排序,若 nums[i] == nums[k-2],表示該值已至少寫入兩次,應跳過。此邏輯可自然推廣到「最多允許 m 次」的版本,只需將條件改為 nums[i] != nums[k-m]。
時間複雜度:O(n) — 只需一次線性掃描整個陣列,每個元素最多被讀取一次、寫入一次。
空間複雜度:O(1) — 所有操作皆就地完成,只使用了兩個整數指標變數(i 和 k),不需要額外的陣列或輔助資料結構。
1. Initialize write pointer k = 0
2. Iterate i from 0 to n-1:
a. Check condition: k < 2 OR nums[i] != nums[k-2]
- k < 2: always write the first two elements
- nums[i] != nums[k-2]: current value not yet written twice
b. If condition is true:
- Write nums[i] into nums[k]
- Increment k
c. Otherwise: skip (element already appears twice in written portion)
3. Return k (the new valid length)方法一:計數器追蹤法 時間複雜度:O(n),空間複雜度:O(1) — 使用一個計數器追蹤當前元素已出現的次數,每換到新元素時重置計數器。當計數器 ≤ 2 時才將元素寫入寫入指標位置。邏輯較直觀但需要額外的計數變數和當前值追蹤。
方法二:使用 STL unique_copy 變體(僅作了解)
時間複雜度:O(n),空間複雜度:O(1) — 概念上等同於自定義謂詞版本的 unique,但標準 STL 的 std::unique 只允許最多一次重複,無法直接用於此題,需自行實作。不建議在面試中使用,因為不夠直觀且難以向面試官解釋。
k < 2 改為 k < m 以及 nums[k-2] 改為 nums[k-m] 即可,這一模式值得記住。