Leetcode-Array-80.删除有序数组中的重复项2

发表于 分类于 ， 阅读次数： 本文字数： 316 阅读时长 ≈ 1 分钟

思路

重点： - 有序 - 原地删除 - 出现次数超过两次的，保留两次

暴力解法-计数

从头遍历，出现一个新的数，将计数变量清零。当计数变量超过2时，删除这个元素，将后续元素前移.

快慢指针

和 26题目 本质上是类似的。

  • 使用 slow 指针标记下一个需要被替换的位置，slow 之前的数列都已经满足要求
  • 使用 fast 指针找到下一个需要移动到 slow 位置的值
1
2
3
4
5
// 伪代码
// 使用一个计数变量，使用一个暂存变量（当前正在计数的值）
// 首先初始化slow找到第一个可以代替的位置
// 将 fast 指针初始化为 slow，并向后边计数边寻找，如果计数变量小于2就移动，如果计数变量大于1就只移动right指针
// 每次移动完值之后，将slow与right+1

突然想到完全没必要使用计数变量，因为是有序的，所以直接使用 nums[i-2]?=nums[i] 就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=2) return nums.length;

        int slow=2, fast=2;

        while(fast<nums.length){
            if(nums[slow-2]!=nums[fast]){// 快指针
                nums[slow]=nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;

    }
}