Remove Duplicates from Sorted Array II

題目說明

給定一組遞增整數數列，刪掉重複出現兩次以上的數(即同一個數最多可出現兩次)並且保持原數列排序。回傳最後留下的個數。

範例

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

限制條件

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

思路

因為數列已排序過，所以不用擔心值亂跳的問題，再根據題目要求，同樣的數可出現兩次，所以多加了一個變數exist判斷是否曾經存在過第二次了

需要處理兩個狀況

1. 當前值未被填過，故需填入數列中，並將exist設為false (因為此值為新加入)
2. 當前值被填過，此時因題目可容許出現兩次，故判斷是否exist為false(可再加一次)，若為true(值已被加兩次了，直接忽略當前值，繼續往後遍歷)。

C++ 程式碼

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 1;
        bool exist = false;
        for (int i=1; i<nums.size(); i++) {
            if (nums[i] != nums[i-1]) {
                nums[k] = nums[i];
                exist = false;
                k++;
            }
            else if (nums[i] == nums[i-1] && !exist) {
                nums[k] = nums[i];
                exist = true;
                k++;
            }
        }
        return k;
    }
};

Python3 程式碼

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 1
        exist = False
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[k] = nums[i]
                k += 1
                exist = False
            elif nums[i] == nums[i-1] and not exist:
                nums[k] = nums[i]
                k += 1
                exist = True
        return k

更佳解 C++ 程式碼

後來去看了其他人分享的解法，發現了更好的做法，或說實際上應該這樣做啦!!! 就是exist應該改成count計數，這樣不管要留幾個重複的數都可以很動態的快速完成

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 1;
        int count = 1;
        for (int i=1; i<nums.size(); i++) {
            if (nums[i] != nums[i-1]) {
                nums[k] = nums[i];
                count = 1;
                k++;
            }
            else if (nums[i] == nums[i-1] && count < 2) {
                nums[k] = nums[i];
                count++;
                k++;
            }
        }
        return k;
    }
};