80. Remove Duplicates from Sorted Array II

Leetcode

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

題目

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.

Custom Judge:

The judge will test your solution with the following code:

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];
}

If all assertions pass, then your solution will be accepted.

Example 1:

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:

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).

解答

• 方法一

利用矩陣的 splice 方法

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  let target = nums[0];
  let count = 0;
  
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      count++;
      if (count > 2) {
        nums.splice(i, 1);
        i--;
      }
    } else {
      target = nums[i];
      count = 1;
    }
  }

  return nums.length;
};

• 方法二 - 快慢指針

慢指針指向重複兩個數字的後面那個數字，快指針遍歷所有矩陣

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  const MAX = 2;
  let count = 1;
  let slow = 0;

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[slow] === nums[fast]) {
      if (count < MAX) {
        count++;
        // 需要把後面的 fast 移到前面 slow 的後面
        // ex. 1, 1, 2(slow), 1, 2(fast)
        // =>  1, 1, 2, 2, 1
        slow++;
        nums[slow] = nums[fast];
      }
    } else {
      slow++;
      nums[slow] = nums[fast];
      count = 1;
    }
  }

  return slow + 1;
};

Runtime: 63 ms Beats 48.93% of users with JavaScript

Memory: 51.42 MB Beats 61.39% of users with JavaScript

• 方法三 - 快慢指針進化版

前一個解法我們用 count 來記錄重複數值的數量是否有超過 2，但其實可以連 count 都不需要，原因是可以拿快指針去與慢指針的前一個元素進行比較

例如：

快指針所在元素跟慢指針的前一個元素比較 (不相等)

1 1 2
  s f
  
1 2 2
  s f 

由於題目給的矩陣是由小到大排序過的，所以當 快指針所在的元素 與 慢指針的前一個元素 不相等時，這個 快指針所在的元素 一定不會是重複的，這時就可以把快指針所在的元素添加進矩陣

而如果 快指針所在的元素 與 慢指針的前一個元素 相等時，代表 快指針所在的元素 已經重複了，所以需要將快指針往後移動

快指針跟慢指針的前一個數值比較

相等的狀況 => 已經重複 => 快指針需要往後移動
1 1 1 1 1 2 2 3
  s   f
  
不相等的狀況 => 不會重複 => 將快指針所在元素移到慢指針的後面
1 1 1 2 2 3 3 3
  s   f

var removeDuplicates = function (nums) {
    if (nums.length === 1) return 1;

    const MAX = 2;
    let slow = 1;

    for (let fast = 2; fast < nums.length; fast++) {
        // 快指針跟慢指針的前一個數值比較
        if (nums[fast] !== nums[slow - MAX + 1]) {
            // 如果數值不相等的話，代表快指針所在的元素一定不是重複的，將這個元素添加進去
            slow++;
            nums[slow] = nums[fast];
        }
    }

    return slow + 1;
};

參考資料

80. Remove Duplicates from Sorted Array II · leetcodeleetcode.wang

測資

let nums = [1,1,1,2,2,3];
nums = [0,0,1,1,1,1,2,3,3];

const result = removeDuplicates(nums)
console.log(nums, result);