题目描述
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.
思路拆解
这个题是Remove Duplicates from Sorted Array的延续。也是插空法的经典题目，甚至可以扩展到Remove Duplicates from Sorted Array N。前两个元素不需要改变，就当已经插入到数组中了。从第三个元素开始，只要遍历的元素和前面两个的元素相同，就跳过。否则，就进行插入。
代码实现
C++版本
class Solution {public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
if (len <= 2) {
return len;
}
int insert_pos = 2;
int i = 2;
while (i < len) {
if (nums[insert_pos - 1] == nums[i] && nums[insert_pos - 2] == nums[i]) {
++i;
continue;
}
else {
nums[insert_pos++] = nums[i++];
}
}
return insert_pos;
}
};
Java版本
class Solution {public int removeDuplicates(int[] nums) {
int len = nums.length;
if (len <= 2) {
return len;
}
int insert_pos = 2;
int i = 2;
while (i < len) {
if (nums[i] == nums[insert_pos - 2] && nums[i] == nums[insert_pos - 1]) {
++i;
continue;
}
else {
nums[insert_pos] = nums[i];
++insert_pos;
++i;
}
}
return insert_pos;
}
}
Python版本
class Solution(object):def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length <= 2:
return length
#i代表的是increasement，逐渐增加的，insert_pos是逐个插入的
insert_pos = 2
i = 2
while i < length:
#当前元素和之前的两个元素都相同的情况下就跳过
if nums[insert_pos - 2] == nums[i] and nums[insert_pos - 1] == nums[i]:
i += 1
continue
else:
nums[insert_pos] = nums[i]
insert_pos += 1
i += 1
return insert_pos