首页 > 代码库 > 80. Remove Duplicates from Sorted Array II
80. Remove Duplicates from Sorted Array II
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.
原地重置: 此时比较的是新数组的倒数第二个, 即与当前元素相同的元素是否加进去两个了
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int index = 0;
for (int item : nums) {
//---重置原则: 不断挑选的当前元素大于新的数组的倒数第二个数, 如果大于倒数第一个数会少加入重复的数, 新数组变短,
//如果大于倒数第三个数, 会多加入重复的数
if (index < 2 || item > nums[index - 2]) {
nums[index++] = item;
}
}
return index;
}
构造辅助计数器, 一指示什么时候加元素, 什么时候重置计数器
这道题跟Remove Duplicates from Sorted Array比较类似，区别只是这里元素可以重复出现至多两次，而不是一次。其实也比较简单，只需要维护一个counter，当counter是2时，就直接跳过即可，否则说明元素出现次数没有超，继续放入结果数组，若遇到新元素则重置counter。总体算法只需要扫描一次数组，所以时间上是O(n)，空间上只需要维护一个index和counter，所以是O(1)。代码如下：
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length <= 2) {
return nums.length;
}
int slow = 1, fast = 1, count = 1;
while (fast < nums.length) {
if (nums[fast] == nums[fast- 1]) {
if (count == 0) {
fast++;
} else {
count--;
nums[slow] = nums[fast];
fast++;
slow++;
}
} else {
count = 1;
nums[slow] = nums[fast];
slow++;
fast++;
}
}
return slow;
}
}
80. Remove Duplicates from Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。