leetcode80.Remove Duplicates from Sorted Array II

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

Remove Duplicates I 可以参考我的这篇博客
这题中添加了一个要求，就是允许存在两个重复值。

思路与代码

其实在这里我们仍然延续I中的思路。在遇到非重复值以及非多余的重复值时，将数值移动到当前记录的下标上。保证该下标前的值均为满足题目条件的值。
第一次我使用了count来记录某个值出现的次数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int removeDuplicates(int[] nums) {
    int length = nums.length;
    if(length<=1){
        return length;
    }
    int index = 1;
    int count = 1;
    for(int i = 1 ; i<nums.length ; i++){
        if(nums[i] == nums[i-1]){
            if(++count>2) continue;
        }else{
            count = 1;
        }
        nums[index++] = nums[i];
    }
    return index;
}

但是看了一下别人的代码，发现既然是有序数组，则可以通过判断该值和前前位置上的值是否相等即可知道该值是否多余。省去了多余的变量。 

1
2
3
4
5
6
7
public int removeDuplicates2(int[] nums) {
    int i = 0;
    for (int n : nums)
        if (i < 2 || n > nums[i-2])
            nums[i++] = n;
    return i;
}