remove duplicates from sorted array ii

• medium
• tagged: array
• similar: remove duplicates from sorted array/list

类似题目I, 只是此时说了duplicates可以有k个. 即重复的元素可以有k个.

思路

• 就是在纸上画, 发现只要判断连续的2个元素是否相同, 不同的话, 则可以复制. 相同的话, 而且是k个的话就可以复制.
• 但是实际写起来发现很乱!

idea

• 参考的好的解法.
• 代码如下:

public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0)  return 0;
    if (nums.length <= 2)  return nums.length;
    int i = 1;
    int cnt = 1;
    for (int j = 1; j < nums.length; ++j) {
      if (nums[j] != nums[j-1]) {
        cnt = 1;
        nums[i++] = nums[j];
      }
      else {
        if (cnt < 2) {
          nums[i++] = nums[j];
          cnt++;
        }
      }
    }
    return i;
}

错误的写法

• 代码如下

public int removeDuplicatesWRONG(int[] nums) {
    if (nums == null || nums.length == 0)  return 0;
    int pre = nums[0];
    int ptr = 0;
    int cnt = 1;
    for (int i = 1; i < nums.length; ++i) {
      if (pre == nums[i])  cnt++;
      else  cnt = 1;
      if (cnt > 2) {
        while (nums[i] == pre) {
          i++;
          if (i == nums.length-1) break;
        }
        cnt = 1;
        pre = nums[i];
        nums[++ptr] = nums[i];
      }
      else {
        nums[++ptr] = nums[i];
        pre = nums[i];
      }
    }

    return ptr+1;
  }