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

題目

給定一個非遞減的整數陣列 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:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

解題思路

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

相關文章

[LeetCode] 27. Remove Element (JS) [LeetCode] 189. Rotate Array (JS) [LeetCode] 238. Product of Array Except Self (JS) [LeetCode] 55. Jump Game (JS) [LeetCode] 26. Remove Duplicates from Sorted Array (JS) [LeetCode] 45. Jump Game II (JS)