題目

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
  • Return k.
  • 題目連結

Example 1

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

解釋題目

給你一個 array ( 叫 nums )，要把 nums 中重複的值去除，題目要求不能用新的 array 紀錄，只能更動原本的 array，最後，要回傳 array 中不重複數字的數量，假設是 k。驗證答案時，只會取 array 中前 k 個值，k 之後的值不會影響驗證。

思路

這題跟 leetcode-27 很像，差異是 leetcode-27 是去除 array 中指定的數字，這題是去除 array 中所有重複的數字，也就是所有數字只能出現一次。

  1. 在一次的 for 迴圈中，把 array 重新排列
  2. 因為要重新排列 array，所以必須有一個 new_index 去記錄 array 中每個位置，決定該位置要放甚麼數字
  3. new_index 會從 1 開始，因為第一個數字，一定不會有重複問題
  4. 遍歷 array 的過程中
    • 如果 array[i] 的值 不等於 前一個數字 array[new_index-1]，array[new_index] 會替換成 array[i]，且 new_index 要往下走一步
    • 如果 array[i] 的值 等於 前一個數字 array[new_index-1]，new_index 維持原位

要注意的是，跟前一個數字比較是用 array[new_index-1] 而不是 array[i-1]，因為 array 是會變動的，但是因為 array[new_index-1] 已經是變動完的結果，所以 new_index 所在位置的前值是確定的。這個前值，也可以用另外的變數表示，這邊可以跟 leetcode-80 比較。

程式碼

1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        new_idx = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[new_idx - 1]:
                nums[new_idx] = nums[i]
                new_idx = new_idx + 1
        return new_idx