[LeetCode]80. Remove Duplicates from Sorted Array II

Question

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.

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

问题解析

问题要求在排序数组中,去掉出现次数超过3次的数字,并且in-place修改,意思是说直接修改,不能创建新的空间,比如新创建一个数组空间,然后统计排序数组中每个数字出现的次数,如果超过3次,不进入新数组,否则进行新数组。最后返回新数组的长度(这里返回新数组的长度,leetcode会根据长度对数组做截取,返回一个新数组,所以测试用例结果是一个数组)。

最初的解决方法是,设定一个”指针”idx指向下标1(从0开始)[因为,前两个一定满足条件,所以我们直接从第3个元素开始看],条件很简单,因为idx指向的是新数组,然后当前下标为i数字等于num[idx],而且nums[idx]等于nums[idx-1]时,我们就跳过,否则,将nums[i]添加到新数组中。伪代码表述如下:

1
2
3
4
5
6
7
8
9
10
11

if (nums length < 2) return nums length;
idx = 1;// 新数组下边界[末尾]
for i: 2 to length:
if nums[i] == nums[idx] and nums[idx] == nums[idx-1]://说明是第三次出现
continue;
else:
idx ++;
nums[idx] = nums[i];

return idx+1;

Version 1

所以,第一版答案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 3) return nums.size();
int idx = 1;//新数组的下边界,指向新数组的末尾

for (int i=2; i< nums.size(); i++){
if (nums[i] == nums[idx-1] && nums[idx] == nums[idx-1])//出现3次,跳过
continue;
else
nums[++idx] = nums[i];//否则,idx先自增[扩建数组容量],将元素放进数组中
}
return idx+1;
}
};

Version 2

Version1中的方法,主要利用了排序数组如果相同元素一定是邻接关系,但是因为是不降序排序,一定会存在nums[i] <= nums[i+1]。所以for循环中判断当前元素是第三次出现的if条件,我们可以修改一下:nums[i] == nums[idx-1]. 原因是数组非递减排序,如果nums[i]等于nums[idx-1],那么nums[i]一定等于nums[idx],因为不递减呀,后面的元素一定大于等于前面的元素(修改后是说,如果当前元素和有序数组末尾的前一个数组相等,那么这个元素一定是第三次出现,我们跳过它)。另一方面,我们也可以把if…else减少为只用if,判断当前元素是否不是第三次出现,Yes,添加到新数组;No,do nothing。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 3) 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;
}
};

Version 3

代码化简,我们将前两个元素也统一进来.元素进入新数组的条件有两个(或关系,满足一个就行;idx新数组下标,从0开始):

  1. idx < 2: 说明是前两个元素
  2. num != nums[idx-2]: 当前元素不等于新数组最后一个元素的前一个;当然不等于也可以改成 >(因为不降序有序数组后面元素一定大于等于前面的元素,目前不是等于,那就剩下大于了O(∩_∩)O)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int idx = 0;// 第一个位置

for (int num : nums){
if (idx < 2 || num > nums[idx-2])// 新数组末尾的前一个元素
nums[idx++] = num;
}
return idx;
}
};
您的支持就是我更新的最大动力!谢谢!