长大后想做什么？做回小孩！

0%

LeetCode——删除排序数组中的重复项II

发表于 更新于 分类于 Valine：
本文字数： 176

NO.80 删除排序数组中的重复项 中等

GPZuPP.png

GPZm5t.png

思路一：双指针 和NO.26删除排序数组中的重复项思路一样采用双指针。区别在于，本题允许重复一次。

所以只要不超过两个的元素都要紧凑到数组靠前的部分，超过两个的部分被覆盖掉。用j指针遍历数组，i指针指向当前符合要求已经被紧凑的部分的结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int removeDuplicates(int[] nums) {
    if (nums == null) return 0;
    if (nums.length < 3) return nums.length;
    int i = 1, j = 1, counter = 1;
    //j遍历数组
    for (; j < nums.length; j++) {
        //如果相等计数器加一，否则置为1
        if (nums[j] == nums[j - 1]) {
            counter++;
        } else {
            counter = 1;
        }
        //如果当前计数器不大于2，将j元素覆盖到i元素上，i移动
        if (counter <= 2) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github