删除有序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入:nums = [1, 1, 2]
输出:2, nums = [1, 2]

快慢指针分别在索引为0和1的位置,慢指针时钟指向不重复序列的最后一位,快指针则否则遍历
遇到与慢指针相同时就继续++,不同时则慢指针后移,将下一个不重复的数字复制过来

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int low = 0, fast = 1;
        while (fast < nums.size()) {
            if (nums[low] != nums[fast]) {//不相等时,快指针复制到慢指针的下一位;相等时只有快指针+1
                low++;
                nums[low] = nums[fast];
            }
            fast++;
        }
        return low + 1;
    }
};

时间复杂度:O(n),假设数组的长度是 n,那么 i 和 j 分别最多遍历 n步。
空间复杂度:O(1)

升级:
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现k次 ,返回删除后数组的新长度。

//------------------------------------way1
class Solution {
public:
    //定义通用函数,使每个元素最多出现k次 
    int remove(vector<int>& nums, int k) {
        if (nums.size() <= k) return nums.size();
        int low = k, fast = k;//low始终指向已排好的新数组的下一位
        while (fast < nums.size()) {
            if (nums[low - k] != nums[fast]) {  // k=2时候  3(low-2) 3 xlow 3(fast) 视为重复,此时low - k=fast
                nums[low] = nums[fast];
                low++;
            }
            fast++;
        }
        return low;
    }
    //------------------------------------way2
public:
    //定义通用函数,使每个元素最多出现k次 
    int remove(vector<int>& nums, int k) {
        if (nums.size() <= k) return nums.size();
        int low = k - 1, fast = k;//low始终指向已排好的新数组的最后一位
        while (fast < nums.size()) {
            if (nums[low - k + 1] != nums[fast]) {  // k=2时候  3(low-1) 3(low) 3(fast) 视为重复,此时 low - k + 1=fast
                low++;
                nums[low] = nums[fast];
            }
            fast++;
        }
        return low + 1;
    }