Remove Duplicates from Sorted Array II

描述

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来记录出现次数。

代码1

  1. // Remove Duplicates from Sorted Array II
  2. // Time complexity: O(n), Space Complexity: O(1)
  3. class Solution {
  4. public:
  5.     int removeDuplicates(vector<int>& nums) {
  6.         if (nums.size() <= 2) return nums.size();
  8.         int index = 2;
  9.         for (int i = 2; i < nums.size(); i++){
  10.             if (nums[i] != nums[index - 2])
  11.                 nums[index++] = nums[i];
  12.         }
  14.         return index;
  15.     }
  16. };

代码2

下面是一个更简洁的版本。上面的代码略长，不过扩展性好一些，例如将occur < 2改为occur < 3，就变成了允许重复最多3次。

  1. // Remove Duplicates from Sorted Array II
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. class Solution {
  4. public:
  5.     int removeDuplicates(vector<int>& nums) {
  6.         const int n = nums.size();
  7.         int index = 0;
  8.         for (int i = 0; i < n; ++i) {
  9.             if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1])
  10.                 continue;
  12.             nums[index++] = nums[i];
  13.         }
  14.         return index;
  15.     }
  16. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/array/remove-duplicates-from-sorted-array-ii.html