【Medium】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.

解法一

用map存每个数及其出现次数，出现一次的，被推上新数组一次，多次的，被推上新数组两次。

解法二

中心思想：

在原数组上进行改变。用两个指针，一个i用来指数组改变到的位置，一个j用来指遍历到的位置。遍历时，判断nums[j]和其下一个数nums[j+1]是否相同，如果相同的话，nums[i]和nums[i+1]都等于这个数，然后，将指针j移到其后面第一个与nums[i]存的数不一样的数，继续遍历，而i也要i+=2，指向存好的两个数之后。如果nums[j]和nums[j+1]不同，则存一次，两个指针同时向后一位。

class Solution { public: int removeDuplicates(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; int i = 0, j = 0; while(i < n && j < n){ if (j+1 < n && nums[j] == nums[j+1]){ nums[i] = nums[j]; nums[i+1] = nums[j]; while(nums[i] == nums[j]){ j++; } i+=2; } else{ nums[i] = nums[j]; i++; j++; } } return i; } };