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^4nums is sorted in non-decreasing order.

思路

因为数列已排序过，所以不用担心值乱跳的问题，再根据题目要求，同样的数可出现两次，所以多加了一个变数exist判断是否曾经存在过第二次了

需要处理两个状况

当前值未被填过，故需填入数列中，并将exist设为false (因为此值为新加入)当前值被填过，此时因题目可容许出现两次，故判断是否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;    }};