[leetcode] 80. Remove Duplicates from Sorted Array II (Medium)

排序数组去重题，保留重复两个次数以内的元素，不申请新的空间。

解法一：

因为已经排好序，所以出现重复的话只能是连续着，所以利用个变量存储出现次数，借此判断。

Runtime: 20 ms, faster than 19.12% of C++ online submissions for Remove Duplicates from Sorted Array II.

class Solution{public:  int removeDuplicates(vector<int> &nums)  {    if (nums.size() == 0)      return 0;    int i = 1;    int lastNum = nums[0];    int times = 1;    while (i < nums.size())    {      if (nums[i] == nums[i - 1])      {        ++times;        if (times > 2)        {          nums.erase(nums.begin() + i);          continue;        }      }      else      {        times = 1;        lastNum = nums[i];      }      i++;    }    return nums.size();  }};

 

解法二：

讨论区看到Stefan Pochmann大神的解法，他的解法一如既往的让人眼前一亮，膜拜啦。

Runtime: 8 ms, faster than 100.00% of C++ online submissions for Remove Duplicates from Sorted Array II.

class Solution { public: int removeDuplicates(vector<int> &nums) { int i = 0; for (int n : nums) if (i < 2 || n > nums[i - 2]) nums[i++] = n; return i; } };

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10014070.html