題目

給定一個非遞減排序（non-decreasing order）的整數 nums 陣列 nums，請 in-place 原地修改原陣列移除所有重複的元素，使每個元素只出現一次，並返回移除重複元素後的陣列長度。

重點 in-place 就是不能回傳一個新的 List

此題已有三個要素

• 陣列已經排序（Sorted）
• 所有重複的元素都會相鄰出現
• 保持 O(1) 額外空間

題目要求：

1. 原地（in-place）移除重複元素
2. 不能用額外的陣列來儲存答案
3. 只能在原陣列 nums 上修改
4. 每個不重複的元素只保留一次
5. 保持原本的相對順序
6. 函式要回傳不重複元素的數量 k

從上述能看出這題目標就是想讓我們達到 O(n) 的時間複雜度和 O(1) 的空間複雜度。

解法一 set 去重 + 排序

順便複習一下 python set 的特點

1. 無序
2. 不重複
3. 不支援索引
4. mutable（可變）

那為何這題不能直接使用 set 去重，因為題目要求是 in-place 修改原陣列，list(set(nums)) 會建立一個新的 list 物件，並沒有改動原本的 nums。

題目也希望使用常數額外空間（O(1) space complexity），而 set(nums) 和 list(…) 都會額外建立新的資料結構，額外空間是 O(n)。

1
2
3
4

# 錯誤寫法
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        unique_list = list(set(nums))

題目要求的是在原陣列上直接修改（in-place），讓前 k 個位置變成去重後的內容。

Custom Judge:

The judge will test your solution with the following code:

1
2
3
4
5
6
7
8
9

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

所以假設還要硬要用 set 來解的話就是，用 set 去重後再排序，然後將結果放回原陣列。

1
2
3
4
5

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        unique_set = sorted(set(nums))
        nums[:len(unique_set)] = unique_set # 將 nums 中前 len(unique_num) 長度的陣列替換成 unique_num
        return len(unique_set)

但這樣的

• 時間複雜度是 O(n log n)，因為排序的時間複雜度是 O(n log n)，不符合題目要求的 O(n)。
  • set(nums) → 將陣列轉成集合，去重
    • 建立集合需要遍歷整個陣列 → O(n)
  • sorted(…) → 集合轉回排序列表
    • 排序複雜度 → O(k log k)，k ≤ n
    • 最壞情況（全部元素不同）就是 O(n log n)
• 空間複雜度是 O(n)，因為建立了新的集合和列表

Two Pointer Fast-Slow 快慢指標

用 Two Pointer 可以 原地修改（in-place）

1. slow → 放下一個不重複數字的位置，同時能告訴我們現在已經有多少個不重複的數字了 Ex: nums[0,…slow-1]，
2. fast → 尋找新數字

1
2
3
4
5
6
7
8
9

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1

        for fast in range(1,len(nums)): # 從 index 1 開始往右找
            if nums[fast] != nums[fast-1]: # 跟上一個數字比，若不一樣就 update 給 slow pointer
                nums[slow] = nums[fast]
                slow +=1
        return slow # 不重複元素的數量

為何從 index 1 開始？

因為 INPUT 的陣列是排好序的，所以相同的數字一定會排在一起。第一個數字 nums[0] 前面沒有任何數字可以跟它重複，所以它一定是唯一的。

所以可以直接保留它，從第二個數字開始檢查，看看有沒有新的不同數字。

• 時間複雜度是 O(n)，因為只需要遍歷一次陣列。
• 空間複雜度是 O(1)，因為只使用了常數額外空間。

• ← Previous Post
• Next Post →