8.删除有序数组中的重复项 II

题目简介

题目解答

解法一：双指针（快慢指针）

思路：本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2]是否和当前待检查元素nums[fast] 相同。当且仅当 nums[slow−2]=nums[fast]时，当前待检查元素 nums[fast]不应该被保留（因为此时必然有nums[slow−2]=nums[slow−1]=nums[fast]。最后，slow即为处理好的数组的长度。

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int slow = 2;
        int fast = 2;
        if (n<=2) {
            return n;
        }
        while (fast < n) {
            if(nums[slow-2] != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
}

代码解析：

判断数组长度是否小于等于2，因为根据题意元素可以重复出现两次，因此数组长度小于等于2时，我们数组最多出现2个相同的元素，直接返回数组长度即可。

这里就是快慢指针判断数组元素是否会重复三次的源代码了，原理就是慢指针与快指针先全部将下标赋值为2，然后慢指针减2与快指针比较(此时就相当于第一次元素和第三个元素比较 - 注题目给的是递增有序数组)，此时无非只有两种情况，间隔两个位置的元素相等或不相等。

如果不相等，我们便可以将慢指针此时指向元素的值赋值为快指针的值然后两个指针都加加。

如果相等，我们便让快指针加加，慢指针不变继续下一次循环。

直到fast快指针的长度大于等于数组长度n，循环就会跳出。

最后返回slow即可，这里的slow更像是一个一个元素拼接而成的新数组。

复杂度分析：

• 时间复杂度：O(n)O(n)O(n)，其中 nnn 是数组的长度。我们最多遍历该数组一次。

• 空间复杂度：O(1)O(1)O(1)。我们只需要常数的空间存储若干变量。

题目链接

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

感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘