26/80-删除有序数组中的重复项

LeetCode 26. Remove Duplicates from Sorted Array

LeetCode

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with $O(1)$ extra memory.

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2。

method: 快慢指针

快指针指向的元素与慢指针-1的元素相比较

• 相同，快指针+1，慢指针不动
• 不同，快指针赋值给慢指针，都+1

int removeDuplicates(vector<int>& nums) {
    if (nums.size() < 1) return nums.size();
    int index = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[index - 1]) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

---

LeetCode 80. Remove Duplicates from Sorted Array II

LeetCode

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

method: 快慢指针

原理一样，只是快指针与慢指针-2的元素相比较

int removeDuplicates(vector<int>& nums) {
    if (nums.size() < 2) return nums.size();
    int index = 2;
    for (int i = 2; i < nums.size(); i++) {
        if (nums[i] != nums[index - 2]) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

总结

如果是允许N个元素重复，快指针与慢指针-N的元素相比较

int removeDuplicates(vector<int>& nums) {
    if (nums.size() < N) return nums.size();
    int index = N;
    for (int i = N; i < nums.size(); i++) {
        if (nums[i] != nums[index - N]) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}