排序数组中的重复项 II（Remove Duplicates from Sorted Array II）

字数 3093 2025-10-27 22:21:43

排序数组中的重复项 II（Remove Duplicates from Sorted Array II）

题目描述
给定一个按非递减顺序排列的整数数组 nums，你需要原地删除重复出现的元素，使得每个元素最多出现两次，并返回删除后数组的新长度。你必须使用 O(1) 的额外空间完成操作。

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

解题过程

问题分析
核心要求是“原地”修改数组，这意味着不能使用额外的 O(n) 空间（例如创建一个新数组）。我们必须在原数组上通过交换或覆盖元素来完成操作。由于数组本身是有序的，相同的数字会连续出现，这大大简化了问题。我们的目标是保留每个数字最多两次。
核心思路：双指针法
这是一个处理有序数组去重或条件过滤的经典方法。我们将使用两个指针：
- slow 指针：指向下一个“合格”元素（即满足“最多出现两次”条件的元素）应该被放置的位置。它同时也标志着当前已经处理好的新数组的末尾。
- fast 指针：用于遍历整个原始数组，检查每个元素。
通俗地讲，fast 指针是“侦察兵”，负责探索前方；slow 指针是“建筑师”，负责在身后构建新的合格数组。
关键判断条件
我们如何决定 nums[fast] 这个元素是否应该被保留到新数组中呢？
由于允许最多重复两次，我们不能简单地比较 nums[slow] 和 nums[fast]。我们需要检查，如果我们将 nums[fast] 放入新数组的当前位置（即 slow 的下一个位置），它是否会导致连续出现超过两次。

一个巧妙的判断方法是：比较 nums[fast] 和 nums[slow - 1]。
- 如果 nums[fast] 不等于 nums[slow - 1]，这意味着当前扫描到的数字，在新数组的最近两个位置中最多只出现了一次（因为数组有序，相同的数字连续），所以我们可以安全地加入它。
- 如果 nums[fast] 等于 nums[slow - 1]，我们需要小心。但这并不直接意味着不能加入。我们需要再往前看一步。如果 nums[fast] 等于 nums[slow - 2]，那就意味着如果加入，这个数字将连续出现第三次（nums[slow-2], nums[slow-1], nums[fast]），这是不允许的。反之，如果不等，说明即使相等，也只会是第二次出现，是允许的。
但是，当 slow 很小（比如小于2）时，slow-1 或 slow-2 可能是无效索引。我们可以换一种更通用的思考方式：只要 nums[fast] 与当前已构建的新数组的倒数第二个元素不同，就可以加入。因为数组是有序的，如果不同，说明加入它不会造成连续三个相同。

更简洁的判断条件是：直接比较 nums[fast] 和 nums[slow - 2]。
- 如果 nums[fast] > nums[slow - 2]，那么 nums[fast] 是一个全新的数字，或者即使相同，由于数组有序，也绝不可能是连续出现的第三个。因为如果相同，那么 nums[slow-1] 必然也等于 nums[slow-2]，这与我们的判断条件矛盾。
- 实际上，由于数组有序，我们只需要检查它们是否不相等。因为如果相等，则 nums[fast] 一定是连续出现的至少第三次。
因此，核心条件简化为：nums[fast] != nums[slow - 2]。

为了处理初始情况（当 slow < 2 时，slow-2 是无效索引），我们可以这样理解：当新数组的长度还小于2时，无论 nums[fast] 是什么，我们都可以直接加入，因为不可能违反“最多出现两次”的规则。
算法步骤
让我们一步步模拟算法过程。
- 步骤 1：初始化
  设置两个指针 slow = 0，fast = 0。slow 表示新数组的末尾（下一个要放入元素的位置）。
- 步骤 2：遍历数组
  使用 fast 指针遍历数组中的每一个元素（fast 从 0 到 nums.length - 1）。
- 步骤 3：判断是否保留当前元素
  对于每个 nums[fast]，进行检查：
  如果 slow < 2 或者 nums[fast] != nums[slow - 2]
  这个条件意味着：
  1. 要么是新数组的长度还不足2（slow < 2），此时加入任何元素都不会导致重复超过两次。
  2. 要么是当前元素 nums[fast] 与新数组中倒数第二个元素 nums[slow-2] 不同。由于数组有序，这保证了即使 nums[fast] 与 nums[slow-1] 相同，也仅仅是第二次出现，是允许的。如果相同，则说明这已经是连续第三次出现，需要跳过。
- 步骤 4：执行操作
  如果步骤 3 的条件满足，说明 nums[fast] 是合格的，应该被保留到新数组中。
  执行操作：nums[slow] = nums[fast]。然后将 slow 指针向后移动一位 (slow++)，以指向下一个空位。
- 步骤 5：循环与返回
  fast 指针继续向后移动，重复步骤 3 和 4，直到遍历完整个数组。
  循环结束后，slow 的值就是新数组的长度，直接返回 slow。
举例说明
以 nums = [1, 1, 1, 2, 2, 3] 为例：
- 初始：slow = 0, fast = 0
  slow<2 成立，nums[0] (1) 放入 nums[0]，数组为 [1, 1, 1, 2, 2, 3], slow=1
- fast=1：
  slow=1 <2 成立，nums[1] (1) 放入 nums[1]，数组为 [1, 1, 1, 2, 2, 3], slow=2
- fast=2：
  slow=2 >=2，检查 nums[2] (1) == nums[0] (1)？相等！这意味着如果放入，会出现三个1，所以跳过。不执行操作。数组不变，slow 仍为 2。
- fast=3：
  slow=2 >=2，检查 nums[3] (2) == nums[0] (1)？不相等！条件满足。
  nums[3] (2) 放入 nums[2]，数组变为 [1, 1, 2, 2, 2, 3], slow=3
- fast=4：
  slow=3 >=2，检查 nums[4] (2) == nums[1] (1)？不相等！条件满足。
  nums[4] (2) 放入 nums[3]，数组变为 [1, 1, 2, 2, 2, 3], slow=4
- fast=5：
  slow=4 >=2，检查 nums[5] (3) == nums[2] (2)？不相等！条件满足。
  nums[5] (3) 放入 nums[4]，数组变为 [1, 1, 2, 2, 3, 3], slow=5
最终返回 slow = 5。数组的前5个元素 [1, 1, 2, 2, 3] 即为所求。

排序数组中的重复项 II（Remove Duplicates from Sorted Array II）题目描述给定一个按非递减顺序排列的整数数组 nums，你需要原地删除重复出现的元素，使得每个元素最多出现两次，并返回删除后数组的新长度。你必须使用 O(1) 的额外空间完成操作。例如：输入：nums = [ 1,1,1,2,2,3 ] 输出：5, nums = [ 1,1,2,2,3,_ ] 解释：函数应返回新长度 5，并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。不需要考虑数组中超出新长度的元素。解题过程问题分析核心要求是“原地”修改数组，这意味着不能使用额外的 O(n) 空间（例如创建一个新数组）。我们必须在原数组上通过交换或覆盖元素来完成操作。由于数组本身是有序的，相同的数字会连续出现，这大大简化了问题。我们的目标是保留每个数字最多两次。核心思路：双指针法这是一个处理有序数组去重或条件过滤的经典方法。我们将使用两个指针： slow 指针：指向下一个“合格”元素（即满足“最多出现两次”条件的元素）应该被放置的位置。它同时也标志着当前已经处理好的新数组的末尾。 fast 指针：用于遍历整个原始数组，检查每个元素。通俗地讲， fast 指针是“侦察兵”，负责探索前方； slow 指针是“建筑师”，负责在身后构建新的合格数组。关键判断条件我们如何决定 nums[fast] 这个元素是否应该被保留到新数组中呢？由于允许最多重复两次，我们不能简单地比较 nums[slow] 和 nums[fast] 。我们需要检查，如果我们将 nums[fast] 放入新数组的当前位置（即 slow 的下一个位置），它是否会导致连续出现超过两次。一个巧妙的判断方法是：比较 nums[fast] 和 nums[slow - 1] 。如果 nums[fast] 不等于 nums[slow - 1] ，这意味着当前扫描到的数字，在新数组的最近两个位置中最多只出现了一次（因为数组有序，相同的数字连续），所以我们可以安全地加入它。如果 nums[fast] 等于 nums[slow - 1] ，我们需要小心。但这并不直接意味着不能加入。我们需要再往前看一步。如果 nums[fast] 等于 nums[slow - 2] ，那就意味着如果加入，这个数字将连续出现第三次（ nums[slow-2] , nums[slow-1] , nums[fast] ），这是不允许的。反之，如果不等，说明即使相等，也只会是第二次出现，是允许的。但是，当 slow 很小（比如小于2）时， slow-1 或 slow-2 可能是无效索引。我们可以换一种更通用的思考方式：只要 nums[fast] 与当前已构建的新数组的倒数第二个元素不同，就可以加入。因为数组是有序的，如果不同，说明加入它不会造成连续三个相同。更简洁的判断条件是：直接比较 nums[fast] 和 nums[slow - 2] 。如果 nums[fast] > nums[slow - 2] ，那么 nums[fast] 是一个全新的数字，或者即使相同，由于数组有序，也绝不可能是连续出现的第三个。因为如果相同，那么 nums[slow-1] 必然也等于 nums[slow-2] ，这与我们的判断条件矛盾。实际上，由于数组有序，我们只需要检查它们是否不相等。因为如果相等，则 nums[fast] 一定是连续出现的至少第三次。因此，核心条件简化为： nums[fast] != nums[slow - 2] 。为了处理初始情况（当 slow < 2 时， slow-2 是无效索引），我们可以这样理解：当新数组的长度还小于2时，无论 nums[fast] 是什么，我们都可以直接加入，因为不可能违反“最多出现两次”的规则。算法步骤让我们一步步模拟算法过程。步骤 1：初始化设置两个指针 slow = 0 ， fast = 0 。 slow 表示新数组的末尾（下一个要放入元素的位置）。步骤 2：遍历数组使用 fast 指针遍历数组中的每一个元素（ fast 从 0 到 nums.length - 1 ）。步骤 3：判断是否保留当前元素对于每个 nums[fast] ，进行检查：如果 slow < 2 或者 nums[fast] != nums[slow - 2] 这个条件意味着：要么是新数组的长度还不足2（ slow < 2 ），此时加入任何元素都不会导致重复超过两次。要么是当前元素 nums[fast] 与新数组中倒数第二个元素 nums[slow-2] 不同。由于数组有序，这保证了即使 nums[fast] 与 nums[slow-1] 相同，也仅仅是第二次出现，是允许的。如果相同，则说明这已经是连续第三次出现，需要跳过。步骤 4：执行操作如果步骤 3 的条件满足，说明 nums[fast] 是合格的，应该被保留到新数组中。执行操作： nums[slow] = nums[fast] 。然后将 slow 指针向后移动一位 ( slow++ )，以指向下一个空位。步骤 5：循环与返回 fast 指针继续向后移动，重复步骤 3 和 4，直到遍历完整个数组。循环结束后， slow 的值就是新数组的长度，直接返回 slow 。举例说明以 nums = [1, 1, 1, 2, 2, 3] 为例：初始： slow = 0 , fast = 0 slow<2 成立， nums[0] (1) 放入 nums[0] ，数组为 [1, 1, 1, 2, 2, 3] , slow=1 fast=1 ： slow=1 <2 成立， nums[1] (1) 放入 nums[1] ，数组为 [1, 1, 1, 2, 2, 3] , slow=2 fast=2 ： slow=2 >=2 ，检查 nums[2] (1) == nums[0] (1) ？相等！这意味着如果放入，会出现三个1，所以跳过。不执行操作。数组不变， slow 仍为 2。 fast=3 ： slow=2 >=2 ，检查 nums[3] (2) == nums[0] (1) ？不相等！条件满足。 nums[3] (2) 放入 nums[2] ，数组变为 [1, 1, 2, 2, 2, 3] , slow=3 fast=4 ： slow=3 >=2 ，检查 nums[4] (2) == nums[1] (1) ？不相等！条件满足。 nums[4] (2) 放入 nums[3] ，数组变为 [1, 1, 2, 2, 2, 3] , slow=4 fast=5 ： slow=4 >=2 ，检查 nums[5] (3) == nums[2] (2) ？不相等！条件满足。 nums[5] (3) 放入 nums[4] ，数组变为 [1, 1, 2, 2, 3, 3] , slow=5 最终返回 slow = 5 。数组的前5个元素 [1, 1, 2, 2, 3] 即为所求。