Site icon May's Notes

[LeetCode] 80. Remove Duplicates from Sorted Array II (JS)

LeetCode Sharing

題目

給定一個非遞減的整數陣列 nums ,就地刪除一些重複項,以便每個唯一元素最多出現兩次(元素的相對順序應保持相同),輸出處理後陣列的長度。

題目 tag 是雙指針,所以盡量用雙指針解決

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

Constraints:

解題思路

non-decreasing order 即非遞減排序,可以是 [1,2,3,4] 也可以是 [1,1,2,2,3,4],所以可以確定相同的整數一定相鄰,這樣就很好辦了。

  1. 如果 nums 的長度小於等於 2 就直接返回 nums.length,因為無需進行操作。
  2. k 初始化為 2,因為前兩個元素一定可以留下來,無需檢查。
  3. 遍歷整個陣列 nums
    • 從索引 2 開始,因為前兩個元素默認可以保留
    • 檢查當前元素 nums[i] 是否與 nums[k-2]nums[k-1] 不相等
      • 不相等代表 nums[i] 是第一次或第二次出現,應該保留
      • nums[i] 寫入到 nums[k] 的位置,然後遞增 k,表示處理了一個新的不重複元素
  4. 最後返回 k,代表處理後的陣列長度

完整程式碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    // 如果 `nums` 的長度小於等於 2 就直接返回 `nums.length`,因為無需進行操作
    if (nums.length <= 2) {
        return nums.length
    }
    // 前兩個元素一定可以留下來,無需檢查
    let k = 2
    
    for (let i = 2; i < nums.length; i++) {
        // nums[i] 是第一次或第二次出現,應該保留
        if (nums[i] != nums[k - 2] || nums[i] != nums[k - 1]) {
            nums[k] = nums[i]
            k++
        }
    }
    return k
};
Exit mobile version