GuilinDev

Lc0080

05 August 2008

80 - Remove Duplicates from Sorted Array II

原题概述

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5

Given 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 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题意和分析

与第26题相比，也是在排好序的Array里面移除重复元素，但是允许元素最多出现两次，思路跟26题也是类似，就是需要额外维护一个计数器counter，同样的元素如果如果counter等于2，直接跳过；遇到新元素时重置counter。

整个数组扫一遍，Time：O(n)；空间上就维护一个index表示最左边可以被取代的位置，然后较快的指针i与index-2位的元素对比（因为index-2的位置可以保证这个元素和index位置的这个元素不一样-大）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
  public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    int slow = 0; //index的意思是最左边的可以被替代的位置
    for (int fast = 0; fast <= nums.length - 1; fast++) {
      if (fast < 2 || nums[fast] != nums[slow - 2]) {
        if (fast != slow) { //这个条件是优化下自己与自己进行赋值,比如[1,2,3,4,5]这种情况
          nums[slow] = nums[fast];
        }
        slow++;
      }
    }
    return slow;
  }
}
This site is open source. Improve this page.