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.

 

// 时间复杂度O(n)  1 class Solution 2 { 3 public: 4     int removeDuplicates(vector
     
      & nums) 5     { 6         if (nums.size() <= 2) // 小于俩数直接返回 7         { 8             return nums.size(); 9         }10 11         int index = 2; // 代表已经去重的nums下标12 13         for (int i = 2; i < nums.size(); ++i) // 从第三个数开始遍历 因为允许两个数重复14         {15             if (nums[i] != nums[index - 2])  // 如果此时index之前两个数不与nums[i]重复就覆盖index这个单元16             {17                 nums[index++] = nums[i];18             }19         }20 21         return index;22     }23 };
     

 

1 // 时间复杂度 0(n) 2 class Solution 3 { 4 public: 5     int removeDuplicates(vector
     
      & nums) 6     { 7         int index = 0; 8         const int n = nums.size(); 9 10         /*11             index和i均从0开始 仅当出现三个重复数时才只增加i的值12         */13         for (int i = 0; i < n; ++i)14         {15             if (i > 0 && i < n - 1 && nums[i - 1] == nums[i] && nums[i] == nums[i + 1])16             {17                 continue;18             }19 20             nums[index++] = nums[i];21         }22 23         return index;24     }25 };
     

 

1 // 时间复杂度 0(n) 2 class Solution 3 { 4 public: 5     int removeDuplicates(vector
     
      & nums) 6     { 7         int index = 0; 8  9         for (auto n : nums)10         {11             if (index < 2 || n > nums[index - 2])12             {13                 nums[index++] = n;14             }15         }16 17         return index;18     }19 };