Aug 15, 2023 2 min read

Leetcode刷題日記 - #26 Remove Duplicates from Sorted Array

題目請自行上Leetcode閱讀：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Sorted Array：只要講到Sorted Array就知道這跟問題應該跟2 pointer有關聯
Return Value, k：題目要求要把Array當中重複的數字移除，不直接宣告一個新的Array，在原本的Array裡面做，最後回傳移除後的Array長度k，如 [1, 2, 2, 3] 最後會變成 [ 1, 2, 3, x] ，k = 3，總之，回傳k = 3的話，即使Array最後長度是4他也不管3以後的數字。除了2 pointer以外，回傳的k數字是一個暗示，在移除重複數字的時候，一定也會不斷地移動k。
如果不常做相似題目，可能一時之間也想不到怎麼解，如果看一個簡單的Array

[1, 2, 2, 2, 3]

在loop這個array的時候，其中一個pointer一定會停留在index 2的位置，等到找到一個跟前面不同的數字的時候，把不同的數字填進去，那這個pointer是什麼？他就是一直指向在目前為止，「沒有重複數字」的Sorted Array的尾，到這裡就明白了k的用意，k就是這個pointer

這題就不畫圖解釋了，基本上就是有一個pointer cur擔任loop array的角色，而k則是負責指向「沒有重複數字」的Sorted Array的尾，當找到下一個不重複的數字時，把現在的數字填入nums[k]。

直得注意的是，為了避免index out of bound，cur並沒有指到最後一個數字，所以最後還是要把最大的數字填進去。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        n = len(nums) - 1
        for cur in range(n):
            if nums[cur] != nums[cur + 1]:
                nums[k] = nums[cur]
                k += 1
        # 把最後的數字填進去
        nums[k] = nums[n]
        return k  + 1

結語：這題的重點在Sorted Array，以及k是指向「沒有重複數字」的Sorted Array的尾。