- 80.
- Given a sorted array nums, remove the duplicates in-place https://en.wikipedia.org/wiki/In-place_algorithm 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 https://en.wikipedia.org/wiki/In-place_algorithm 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.
- Clarification:
- Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
- Internally you can think of this:
- // nums is passed in by reference. (i.e., without making a copy)
- int len = removeDuplicates(nums);
- // any modification to nums in your function would be known by the caller.
- // using the length returned by your function, it prints the first len elements.
- for (int i = 0; i <len; i++) {
- print(nums[i]);
- }
题目要求数组中的重复数字不能超过 2 个, 求出符合要求的数组长度. 并且按照这个长度取出的数组要符合重复数字不超过 2 个的要求, 因此要用后边的元素将多余的元素覆盖掉.
- class Solution {
- public:
- int removeDuplicates(vector<int>& nums) {
- if(nums.size()<2)return nums.size();
- int flag=0,cur=1,count=1;
- while(cur<nums.size()){
- if(nums[flag]==nums[cur] && count==0)++cur;
- else{
- if(nums[flag]==nums[cur])--count;
- else{
- count=1;
- }
- nums[++flag]=nums[cur++];
- }
- }
- return flag+1;
- }
- };
使用 flag 记录符合要求的数组当前位置, 即 flag 以前 (包括 flag 本身) 的数组中重复元素不超过 2 个, 定义名为 cur 的迭代器, 当数组中 cur 所对应的值与 flag 对应的值不相同时, 就从 cur 开始对数组进行覆盖.
为了使 flag 停在正确的位置, 使用 count 来计数重复元素的个数. 当 count 为 0, 即达到最大重复长度 2 时, 只让 cur 向前探索直到找到异类.
只要 cur 和 flag 对应的元素不相等或者 count 不为 0 就执行 nums[++flag]=nums[cur++]; 保证了后边数组向前的覆盖.
参考: https://www.cnblogs.com/grandyang/p/4329295.html
[LeetCode] Remove Duplicates from Sorted Array II
来源: http://www.bubuko.com/infodetail-3043014.html