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

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

快慢指针方法：slow-2指针用来指向第一个未重复的数，fast用来指向slow+2的位置，判断两个指针指向的数是否重复，若重复fast++；若不重复slow位置的数组存储fast位置的值。

1. 首先，如果数组的长度小于或等于2，那么数组中的元素不会重复超过2次，因此直接返回数组的长度 nums.length。
2. 定义两个指针 fast 和 slow，它们都初始化为2。这是因为在允许至多两个重复元素的情况下，前两个元素是允许出现两次的。
3. 使用 fast 指针从索引2开始遍历数组，同时使用 slow 指针来跟踪可以存储新元素的位置。
4. 在循环中，对于每个元素 nums[fast]，检查它是否与 nums[slow-2] 相等。如果不相等，表示这是一个新的不同的元素，可以将其存储在 nums[slow] 的位置，同时递增 slow 指针。
5. 无论元素是否相等，都递增 fast 指针以遍历数组。
6. 循环结束后，slow 指针的位置将指向新数组的末尾，因此返回 slow 作为新数组的长度。

这个算法通过使用两个指针，有效地从已排序的数组中移除重复元素，同时保留至多两个相同的元素。这种解决方案的时间复杂度为 O(n)，其中 n 是数组的长度，因为只遍历了一次数组。这种方法在处理类似问题时非常有用。

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

计数法

1. 创建变量 count 和 start，它们分别用于跟踪每个不同元素的出现次数和新数组的下一个位置。初始时，count 设置为1，因为第一个元素不需要检查重复次数，而 start 设置为1，因为第一个元素将被保留。
2. 从数组的第二个元素开始（索引1），遍历整个数组。
3. 对于每个元素 nums[i]，检查它是否等于前一个元素 nums[i-1]：
   • 如果不相等，表示找到一个新的不同元素，将 count 重置为1，然后将该元素存储在新数组的 start 位置，然后递增 start。
   • 如果相等且 count 等于1，表示这是第二次出现该元素，将该元素存储在新数组的 start 位置，然后递增 start。
4. 继续遍历整个数组。
5. 循环结束后，start 的值将表示新数组的长度。

class Solution {
    public int removeDuplicates(int[] nums) {
        int count=1;
        int start=1;

        for(int i=1;i<nums.length;i++){
            if(nums[i] != nums[i-1]){
                count = 1;
                nums[start]=nums[i];
                start++;
            }else if(count==1){
                count++;
                nums[start] = nums[i];
                start++;
            }
        }
        return start;
    }
}