leetcode：80. 删除有序数组中的重复项 II

题目来源

题目描述

题目解析

这道题是leetcode：26. 删除排序数组中的重复项的扩展

思路一

为了让解法更具有一般性，我们将原问题的「保留 2 位」修改为「保留 k 位」。

对于此类问题，我们应该进行如下考虑：

• 由于是保留k个相同数字，对于前k个元素，一定会保留
• 对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第k个元素进行比较，不相同则保留。

举个例子，们令 k=2，假设有如下样例

[1,1,1,1,1,1,2,2,2,2,2,2,3]

• 首先我们先让前 2 位直接保留，得到 1,1
• 对后面的每一位进行继续遍历，能够保留的前提是与当前位置的前面 k 个元素不同（答案中的第一个 1），因此我们会跳过剩余的 1，将第一个 2 追加，得到 1,1,2
• 继续这个过程，这时候是和答案中的第 2 个 1 进行对比，因此可以得到 1,1,2,2
• 这时候和答案中的第 1 个 2 比较，只有与其不同的元素能追加到答案，因此剩余的 2 被跳过，3 被追加到答案：1,1,2,2,3

class Solution {
    
public:
    int work(vector<int>& nums, int k) {
    
        int len = 0;
        for(auto num : nums)
            if(len < k || nums[len-k] != num)
                nums[len++] = num;
        return len;
    }
    int removeDuplicates(vector<int>& nums) {
    
        return work(nums, 2);
    }
};

思路二

利用快排双色分区partition思想，O(N)，O(1)

维护两个指针，将数组分成三个区：

• [0 … validRange]为有效区（全是有效数）
• (validRange … curIndex)为垃圾区（全是垃圾数）
• [curIndex …]为未知区（还没看的数）

同时记录前一个数preNum和当前数出现次数count，遍历每个数，判断是否垃圾：

• 当前数首次出现，有效数，发货到有效区，同时扩充有效区；
• 当前数出现次数<2，有效数，发货到有效区，同时扩充有效区；
• 当前数出现次数已经>=2，垃圾数，扩充垃圾区；

最后返回有效区的长度即可（validRange+1）

class Solution {
    
public:
    int removeDuplicates(vector<int>& arr) {
    
        int n = arr.size();
        if(n <= 2){
    
            return n;
        }

        // [0 ... validRange]为有效区，(validRange ... curIndex)为垃圾区，[curIndex ...]为未知区
        int validRange = 0, curIndex = 1; // 有效区右边界，当前处理位置
        int preNum = arr[0], count = 1; // 前一个数，出现次数

        while (curIndex < n) {
    
            int curNum = arr[curIndex];
            if (curNum != preNum) {
     // 当前数首次出现，有效数
                arr[++validRange] = arr[curIndex++]; // 发货到有效区，扩充有效区
                preNum = curNum; // 记录该数
                count = 1;
            } else if (count < 2) {
     // 当前数出现次数<2，有效数，发货到有效区，扩充有效区
                arr[++validRange] = arr[curIndex++]; // 发货到有效区，扩充有效区
                count++;
            } else {
     // 当前数出现次数已经>=2，垃圾数
                curIndex++; // 扩充垃圾区
            }
        }

        return validRange + 1;
    }
};