删除有序数组中的重复项II 的题解

题目详情

给你一个有序数组 nums ，请你 原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

1
2
3
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

解题思路与题解

类似这种题一般来说喔们上来就是双指针，来进行解题，so ，接下来我们用双指针的解题方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int removeDuplicates(int[] nums) {
    int k = 2; // 每个元素最多出现的次数
    if (nums.length <= k) return nums.length; // 如果数组长度小于等于 k，直接返回数组长度

    // 初始化慢指针和快指针
    int slow = k;
    int fast = k;
    while (fast < nums.length) {
        // 如果 nums[fast] 不等于 nums[slow - k]
        // 则将 nums[fast] 复制到 nums[slow]，并将 slow 向前移动一位
        if (nums[fast] != nums[slow - k]) { //nums[slow - k] 是当前考虑的元素在新数组中的第一个可能的位置
            nums[slow] = nums[fast];
            slow++;
        }
        // 将 fast 向前移动一位，以检查下一个元素
        fast++;
    }
    // 返回新数组的长度
    return slow;
}

当然，因为我们本题，在题干中明确表示出了，该数组已按升序排列，所以我们有一种更为简便的方法来及逆行编码，此题解也是leetcode官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int removeDuplicates(int[] nums) {
      if (nums.length < 3) return nums.length;
      // 初始化慢指针和快指针，默认我们可以保留两个重复的元素
      int i = 2, j = 2;
      // 当快指针小于数组长度时，执行循环体
      while (j < nums.length) {
          // 如果 nums[j] 不等于 nums[i - 2]，此时我们将快指针的值复制到慢指针的位置，并将慢指针向前移动一位
          // eg : [1,1,1,2,2,3]  i = 2, j = 3 此时 nums[j] = 2, nums[i - 2] = 1 此时两位数不相等，我们将 nums[j] 复制到 nums[i] 的位置
          // 于是数组就变成了 [1,1,2,2,2,3] 此时 i = 3, j = 4 等到下一次执行完循环体之后，数组将变成 [1,1,2,2,3,3]，
          // 此时 i = 4, j = 5 此时我们将慢指针的值return出去即可
          if (nums[j] != nums[i - 2]) {
              nums[i++] = nums[j];
          }
          // 将快指针向前移动一位，以检查下一个元素
          j++;
      }
      // 返回慢指针的值
      return i;
  }

总代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class MultiplePointer {

    public static void main(String[] args) {
        int[] nums = {1, 1,1, 2,2,3,3,3};
        int i = removeDuplicatesB(nums);
        System.out.println(i);
        System.out.println("=============");
        Arrays.stream(nums)
                .limit(i)
                .forEach(System.out::println);
    }

    public static int removeDuplicatesA(int[] nums) {
        int k = 2; // 每个元素最多出现的次数
        if (nums.length <= k) return nums.length; // 如果数组长度小于等于 k，直接返回数组长度

        // 初始化慢指针和快指针
        int slow = k;
        int fast = k;
        while (fast < nums.length) {
            // 如果 nums[fast] 不等于 nums[slow - k]
            // 则将 nums[fast] 复制到 nums[slow]，并将 slow 向前移动一位
            if (nums[fast] != nums[slow - k]) { //nums[slow - k] 是当前考虑的元素在新数组中的第一个可能的位置
                nums[slow] = nums[fast];
                slow++;
            }
            // 将 fast 向前移动一位，以检查下一个元素
            fast++;
        }
        // 返回新数组的长度
        return slow;
    }


    public static int removeDuplicatesB(int[] nums) {
        if (nums.length < 3) return nums.length;
        // 初始化慢指针和快指针，默认我们可以保留两个重复的元素
        int i = 2, j = 2;
        // 当快指针小于数组长度时，执行循环体
        while (j < nums.length) {
            // 如果 nums[j] 不等于 nums[i - 2]，此时我们将快指针的值复制到慢指针的位置，并将慢指针向前移动一位
            // eg : [1,1,1,2,2,3]  i = 2, j = 3 此时 nums[j] = 2, nums[i - 2] = 1 此时两位数不相等，我们将 nums[j] 复制到 nums[i] 的位置
            // 于是数组就变成了 [1,1,2,2,2,3] 此时 i = 3, j = 4 等到下一次执行完循环体之后，数组将变成 [1,1,2,2,3,3]，
            // 此时 i = 4, j = 5 此时我们将慢指针的值return出去即可
            if (nums[j] != nums[i - 2]) {
                nums[i++] = nums[j];
            }
            // 将快指针向前移动一位，以检查下一个元素
            j++;
        }
        // 返回慢指针的值
        return i;
    }

}

image-20231211214200297

宫水三叶大佬版题解，过于牛逼

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) {   
        return process(nums, 2);
    }
    int process(int[] nums, int k) {
        int u = 0; 
        for (int x : nums) {
            if (u < k || nums[u - k] != x) nums[u++] = x;
        }
        return u;
    }
}
/*
作者：宫水三叶
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/