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的时机。这种方法比较复杂，谢谢 @meishenme 提供的简洁方法，核心思想仍然是两根指针，只不过此时新索引自增的条件是当前遍历的数组值和『新索引』或者『新索引-1』两者之一不同。

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() <= 2) return nums.size();
  10.         int len = nums.size();
  11.         int newIndex = 1;
  12.         for (int i = 2; i < len; ++i) {
  13.             if (nums[i] != nums[newIndex] || nums[i] != nums[newIndex - 1]) {
  14.                 ++newIndex;
  15.                 nums[newIndex] = nums[i];
  16.             }
  17.         }
  19.         return newIndex + 1;
  20.     }
  21. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param A: a array of integers
  4.      * @return : return an integer
  5.      */
  6.     public int removeDuplicates(int[] nums) {
  7.         if (nums == null) return -1;
  8.         if (nums.length <= 2) return nums.length;
  10.         int newIndex = 1;
  11.         for (int i = 2; i < nums.length; i++) {
  12.             if (nums[i] != nums[newIndex] || nums[i] != nums[newIndex - 1]) {
  13.                 newIndex++;
  14.                 nums[newIndex] = nums[i];
  15.             }
  16.         }
  18.         return newIndex + 1;
  19.     }
  20. }

源码分析

遍历数组时 i 从2开始，newIndex 初始化为1便于分析。

复杂度分析

时间复杂度 O(n), 空间复杂度 O(1).