Remove Duplicates from Sorted Array II

Question

• lintcode: (101) Remove Duplicates from Sorted Array II

  1. Follow up for "Remove Duplicates":
     2. What if duplicates are allowed at most twice?
     3. 4. For example,
     4. Given sorted array A = [1,1,1,2,2,3],
     5. 7. Your function should return length = 5, and A is now [1,1,2,2,3].
     6. 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.         }
    11.   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.         }
    24.   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