Remove Duplicates from Sorted Array II

Question

  1. Follow up for "Remove Duplicates":
  2. What if duplicates are allowed at most twice?
  4. For example,
  5. Given sorted array A = [1,1,1,2,2,3],
  7. Your function should return length = 5, and A is now [1,1,2,2,3].
  8. Example

題解

在上題基礎上加了限制條件元素最多可重複出現兩次。因此可以在原題的基礎上添加一變量跟蹤元素重複出現的次數，小於指定值時執行賦值操作。但是需要注意的是重複出現次數occurence的初始值(從1開始，而不是0)和reset的時機。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: a list of integers
  5.      * @return : return an integer
  6.      */
  7.     int removeDuplicates(vector<int> &nums) {
  8.         if (nums.size() < 3) {
  9.             return nums.size();
  10.         }
  12.         int size = 0;
  13.         int occurence = 1;
  14.         for (vector<int>::size_type i = 1; i != nums.size(); ++i) {
  15.             if (nums[size] != nums[i]) {
  16.                 nums[++size] = nums[i];
  17.                 occurence = 1;
  18.             } else if (nums[size] == nums[i]) {
  19.                 if (occurence++ < 2) {
  20.                     nums[++size] = nums[i];
  21.                 }
  22.             }
  23.         }
  25.         return ++size;
  26.     }
  27. };

源碼分析

  1. 在數組元素小於3(即為2)時可直接返回vector數組大小。
  2. 初始化occurence的值為1，而不是0. 理解起來也方便些。
  3. 初始化下標值i從1開始
    • nums[size] != nums[i]時遞增size並賦值，同時重置occurence的值為1
    • (nums[size] == nums[i])時，首先判斷occurence的值是否小於2，小於2則先遞增size，隨後將nums[i]的值賦給nums[size]。這裡由於小標i從1開始，免去了對i為0的特殊情況考慮。
  4. 最後返回size + 1，即為++size