題目

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

  • Return k after placing the final result in the first k slots of nums.

  • Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

  • 題目連結

Example 1

1
2
3
4
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2

1
2
3
4
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

解釋題目

給你一個 array ( 叫 nums )，要去除重複出現大於 2 次的數字。也就是說，重複的數字最多可以出現 2 次，不能出現多於 2 次。題目驗證的條件是: 不能用新的 array 紀錄，只能更動原本的 array，最後，要回傳 array 中，最多重複 2 次數字的總數量，假設是 k，驗證答案時，只會取 array 中前 k 個值，k 之後的值不會影響驗證。

思路 (1)

跟 leetcode-26 有點類似，不過這次是可以出現重複數字，只是不能超過 2 次。

  1. 在一次的 for 迴圈中，把 array 重新排列。
  2. 新建立一個 new_index = 1，去記錄 nums 中，紀錄要被替換的位置，new_index 要從 1 開始。
  3. 「前值」用變數 previous 去特別紀錄，一開始是 nums[0]，會在替換的時候變成 nums[i]，這邊就呼應 leetcode-26 之前提到的，因為 array 會變動，所以用 array[i-1] 紀錄前值並不合適。
  4. 用變數 record 紀錄重複數字出現次數，一開始 record = 1，當 nums[i] 等於 previous 值的時候， record 要 + 1 次
  5. 當 nums[i] 不等於 previous 值的時候，代表出現新數字，record 變回 1
  6. 有兩種情況要替換 array 中的值，替換後， new_index 要 往下走一步
    1. nums[i] 等於 previous，且 record < 2 ( 雖然是維持原值，但其實也可以想成在做替換 )
    2. nums[i] 不等於 previous

圖像拆解

步驟拆解 1

步驟拆解 2

步驟拆解 3

步驟拆解 4

步驟拆解 5

步驟拆解 6

步驟拆解 7

步驟拆解 8

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        new_idx = 1
        record = 1
        previous = nums[0]
        for i in range(1, len(nums)):
            # 有兩種情況替換
            if nums[i] == previous and record < 2:
                nums[new_idx] = nums[i]
                new_idx = new_idx + 1
                record = record + 1
            elif nums[i] != previous:
                nums[new_idx] = nums[i]
                new_idx = new_idx + 1
                previous = nums[i]
                record = 1
        return new_idx

思路 (2)

看到網路上大神的寫法，雖然很不直覺，但可以稍微理解一下:

  1. i 是 new_index，因為可以有 2 個重複的數字，所以 i 從「第三個」開始移動，前兩個一定要做替換 ( 維持原值 )。
  2. 遍歷 array 中的數字，當 array[i] 的值 > 前兩個位置的數字，要做替換。替換時， i 要往下移動一步，當 array[i] 的值 ≤ 前兩個位置的數字，i 就不動

程式碼 (2)

1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for n in nums:
            if i < 2 or n > nums[i-2]:
                nums[i] = n
                i += 1
        return i