[LeetCode]80. Remove Duplicates from Sorted Array II

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Given 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 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Solution

Analysis

和[LeetCode]26. Remove Duplicates from Sorted Array要求类似: 有序数组,删除重复数字, 不过这里允许同一数字出现两次, 最多出现两次. 空间复杂度为O(1). 不能使用声明额外的存储空间.

同样,因为数组是有序的,重复数字在数组中位置一定是连续的,比如[1,1,1,2,2,3]. 三个1位置上是连续出现的. 同样使用双指针, 一个指向结果的有序数组idx,一个指向原始数组i. i从下标2开始判断, 如果它和结果有序数组idx-1的数字相等,说明这个数字是第三次出现,跳过它,否则, 加入到结果的有序数组中.

Code

Method One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();

        int idx = 1;

        for (int i=2; i< nums.size(); i++)
            if (nums[i] != nums[idx-1])
                nums[++idx] = nums[i];

        return idx+1;
    }
};

也可以将初始的判断条件和下面的业务操作合并到一起. 原始数组的指针i从0开始, 结果数组指针idx也从0开始,这时候idx表示结果数组中可以存放元素的位置下标, 存放时,直接放入就行. 和上面的方法不同,上面idx指向结果数组的右边界,存放时要先开拓空间. 此时,存放的条件变为当前数和idx-2位置的数不相等. idx-1为有序数组的右边界,idx-2就是前两个位置的数, 不相等时说明这个数是第一次或第二次出现,是满足条件的, 如果相等,说明是第三次出现, 跳过.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int idx = 0;

        for (int num: nums){
            if (idx < 2 || nums[idx-2] != num)
                nums[idx++] = num;
        }

        return idx;
    }
};

还有另一种方法, 直接根据题目要求, 如果当前数是第三次出现跳过它,否则存储到新数组中. 第三次出现怎么表示呢? 当i>=2时,开始判断, nums[i] == nums[idx-1] && nums[i] == nums[idx-2]; 因为当i<2时,之前的数最多出现两次,满足条件.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int idx = 0;
        
        for (int i=0; i< nums.size(); ++i){
            if (i >=2 && nums[i] == nums[idx-1] && nums[idx-1] == nums[idx-2])
                continue;
            nums[idx++] = nums[i];
        }
        
        return idx;
    }
};

类似问题

[LeetCode]26. Remove Duplicates from Sorted Array

您的支持就是我更新的最大动力!谢谢!