Remove Duplicates from Sorted Array II

/* Description: Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3] */ /* 分析： 加一个变量记录一下出现的次数即可，因为题目是已经排序好了的数组，所以一个变量即可解决。 如果是没有排序的数组，则需要引入一个hashmap来记录出现的次数。 */

方法一

// LeetCode, Remove Duplicates from Sorted Array II // 时间复杂度 O(n)空间复杂度(1) #include<iostream> #include<vector> using namespace std; class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.size() <= 2){ return nums.size(); } int index = 2; for (int i = 2; i < nums.size(); i++){ if (nums[i] != nums[index - 2]){ nums[index++] = nums[i]; } } return index; } }; int main(){ Solution a; vector<int> nums; nums.push_back(1); nums.push_back(1); nums.push_back(2); nums.push_back(2); nums.push_back(2); nums.push_back(3); nums.push_back(3); nums.push_back(4); int b=a.removeDuplicates(nums); cout<<b; return 0; } /* 方法一的想法是，我只考虑当前的元素是否和它之前2个偏移位置的元素相同，比如第2个元素和第0个元素是否相同，第3个元素和第1个元素是否相同。 */

方法二

// LeetCode, Remove Duplicates from Sorted Array II // 时间复杂度O(n) 空间复杂度O(1) #include<iostream> #include<vector> #include <algorithm> using namespace std; class Solution { public: int removeDuplicates(vector<int>& nums) { const int n = nums.size(); int index = 0; for (int i = 0; i < n; ++i) {//注意这儿是++i,体会下这儿的小trick(第一次进入循环体时,i=1;避免下面if条件中出现nums[-1]) if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1]){ continue;//注意这儿是 i < n - 1,避免if条件中出现nums[n] } nums[index++] = nums[i]; } return index; } }; int main(){ Solution a; vector<int> nums; nums.push_back(1); nums.push_back(1); nums.push_back(2); nums.push_back(2); nums.push_back(2); nums.push_back(3); nums.push_back(3); nums.push_back(4); int b=a.removeDuplicates(nums); cout<<b; return 0; } /* 方法二的思维比较直观且易理解，我只考虑当前的元素是否和它之前、之后的2个元素相同，是的话，我就ignore这个元素，这样下来，一旦有重复的元素，那么最多2个。 */

总结

方法二是一个较简洁的版本;方法一的扩展性更好，例如将occur < 2改为occur < 3,就变成了允许重复最多3次。