排序数组中的重复项 II（Remove Duplicates from Sorted Array II）的进阶：最多允许K次重复

字数 3117 2025-10-28 00:29:09

排序数组中的重复项 II（Remove Duplicates from Sorted Array II）的进阶：最多允许K次重复

题目描述：
给定一个已经按升序排列的整数数组 nums，以及一个整数 k。你的任务是“就地”修改这个数组，使得每个元素在数组中出现的次数不超过 k 次。你需要保持这些元素的相对顺序不变，并且需要返回修改后数组的新长度。

你不需要考虑数组中超出新长度后面的元素。

示例：
假设 nums = [1, 1, 1, 2, 2, 3], k = 2。
目标：处理后，数组应变为类似 [1, 1, 2, 2, 3]，并且函数返回新长度 5。

解题过程：

这是一个通用化的问题。当 k=1 时，就是标准的“删除排序数组中的重复项”问题；当 k=2 时，就是“删除排序数组中的重复项 II”。我们将设计一个适用于任意 k 的通用解法。

核心思路：双指针法
我们将使用两个指针：slow 和 fast。

slow 指针：指向下一个即将被放置合规元素的位置。也就是说，[0, slow-1] 这个区间是我们已经处理好的、满足“每个元素最多出现 k 次”要求的子数组。
fast 指针：用于遍历整个原始数组，探索待处理的元素。

关键在于，我们如何判断一个元素是否可以放入 slow 位置？

循序渐进的分析：

特殊情况处理：
如果数组 nums 为空，那么新长度自然为 0。如果 k 非常大（比如大于等于数组长度），那么意味着允许所有重复，我们直接返回原数组长度即可。
一般情况：
由于数组是排序的，所有相同的数字会紧挨在一起。对于当前 fast 指针指向的数字 nums[fast]，我们需要判断它是否可以被加入到已处理的“合规”数组（即 [0, slow-1] 区间）中。
判断逻辑：
我们不能简单地比较 nums[slow] 和 nums[fast]，因为我们需要控制重复次数。我们需要向前看，看在当前已处理的数组中，nums[fast] 这个数字已经出现了多少次。
- 如果 nums[fast] 是一个全新的数字（即它与 nums[slow-1] 不同），那么它肯定可以加入。因为一个数字第一次出现，次数为1，小于等于 k。
- 如果 nums[fast] 与 nums[slow-1] 相同，说明我们正在处理一个重复的数字。这时我们需要检查，这个数字在已处理的数组里已经出现了多少次。但是，我们不需要每次都从头开始计数，因为数组是有序的，相同的数字是连续的。我们只需要检查 nums[fast] 是否与 nums[slow - k] 相同。
  - 如果 nums[fast] == nums[slow - k]，这意味着如果把 nums[fast] 放到 slow 位置，那么在 [slow-k, slow] 这个长度为 k+1 的区间内，就全是 nums[fast] 这个数字了（因为 [slow-k, slow-1] 已经是 k 个相同的数）。这就超过了 k 次的限制。因此，这个 nums[fast] 不能要，我们直接移动 fast 指针，跳过它。
  - 如果 nums[fast] != nums[slow - k]，这意味着即使我们把 nums[fast] 放进去，在已处理的数组末尾，nums[fast] 这个数字的出现次数也严格小于 k。因此，这个 nums[fast] 是可以加入的。
为什么比较 nums[slow - k] 是有效的？
因为数组是有序的。如果当前已处理的数组末尾的 k 个元素（即 [slow-k, slow-1]）都是同一个值 x，那么 nums[slow - k] 的值就是 x。如果 nums[fast] 也等于 x，那么加入它就会导致出现 k+1 次。反之，如果 nums[slow - k] 不是 x，说明在 [slow-k, slow-1] 这个区间内，x 出现的次数肯定小于 k（因为如果等于 k，它们必须是连续的 k 个 x，那么 nums[slow-k] 就一定是 x）。
算法步骤：
- 初始化 slow = 0, fast = 0。
- 当 fast 小于数组长度 n 时，执行循环：
  a. 判断是否可放置： 检查 slow 是否小于 k。如果小于，说明当前合规数组长度还不足以构成一个完整的 k 次重复检查窗口，那么 nums[fast] 可以直接放入（因为无论如何都不会超过 k 次）。
  b. 如果 slow >= k，则需要用上述逻辑判断：检查 nums[fast] 是否等于 nums[slow - k]。
  - 如果相等，说明 nums[fast] 放入会导致重复超过 k 次。我们只移动 fast++，跳过它。
  - 如果不相等，说明 nums[fast] 可以放入。
  c. 对于可以放入的情况（即步骤 a 或步骤 b 中“不相等”的情况）：
  - 将 nums[fast] 的值赋给 nums[slow]。
  - 然后同时移动 slow 和 fast 指针：slow++, fast++。
- 循环结束后，slow 的值就是新的数组长度。
示例推演（nums = [1,1,1,2,2,3], k=2）：
- 初始：slow=0, fast=0, nums[0]=1。
  - slow=0 < k=2，直接放入。nums[0]=1。slow=1, fast=1。
- 现在：slow=1, fast=1, nums[1]=1。
  - slow=1 < k=2，直接放入。nums[1]=1。slow=2, fast=2。
- 现在：slow=2, fast=2, nums[2]=1。
  - slow=2 >= k=2，检查 nums[2] (1) == nums[2-2] (nums[0]=1)？相等！跳过。只移动 fast=3。
- 现在：slow=2, fast=3, nums[3]=2。
  - slow=2 >= k=2，检查 nums[3] (2) == nums[2-2] (nums[0]=1)？不相等！放入。nums[2]=2。slow=3, fast=4。
- 现在：slow=3, fast=4, nums[4]=2。
  - slow=3 >= k=2，检查 nums[4] (2) == nums[3-2] (nums[1]=1)？不相等！放入。nums[3]=2。slow=4, fast=5。
- 现在：slow=4, fast=5, nums[5]=3。
  - slow=4 >= k=2，检查 nums[5] (3) == nums[4-2] (nums[2]=2)？不相等！放入。nums[4]=3。slow=5, fast=6。
- 循环结束。新数组为 [1, 1, 2, 2, 3]，长度为 slow=5。

这个算法的时间复杂度是 O(n)，只需要遍历一次数组。空间复杂度是 O(1)，只使用了常数级别的额外空间。它高效地解决了“最多允许K次重复”的通用问题。

排序数组中的重复项 II（Remove Duplicates from Sorted Array II）的进阶：最多允许K次重复题目描述：给定一个已经按升序排列的整数数组 nums ，以及一个整数 k 。你的任务是“就地”修改这个数组，使得每个元素在数组中出现的次数不超过 k 次。你需要保持这些元素的相对顺序不变，并且需要返回修改后数组的新长度。你不需要考虑数组中超出新长度后面的元素。示例：假设 nums = [1, 1, 1, 2, 2, 3] , k = 2 。目标：处理后，数组应变为类似 [1, 1, 2, 2, 3] ，并且函数返回新长度 5。解题过程：这是一个通用化的问题。当 k=1 时，就是标准的“删除排序数组中的重复项”问题；当 k=2 时，就是“删除排序数组中的重复项 II”。我们将设计一个适用于任意 k 的通用解法。核心思路：双指针法我们将使用两个指针： slow 和 fast 。 slow 指针：指向下一个即将被放置合规元素的位置。也就是说， [0, slow-1] 这个区间是我们已经处理好的、满足“每个元素最多出现 k 次”要求的子数组。 fast 指针：用于遍历整个原始数组，探索待处理的元素。关键在于，我们如何判断一个元素是否可以放入 slow 位置？循序渐进的分析：特殊情况处理：如果数组 nums 为空，那么新长度自然为 0。如果 k 非常大（比如大于等于数组长度），那么意味着允许所有重复，我们直接返回原数组长度即可。一般情况：由于数组是排序的，所有相同的数字会紧挨在一起。对于当前 fast 指针指向的数字 nums[fast] ，我们需要判断它是否可以被加入到已处理的“合规”数组（即 [0, slow-1] 区间）中。判断逻辑：我们不能简单地比较 nums[slow] 和 nums[fast] ，因为我们需要控制重复次数。我们需要向前看，看在当前已处理的数组中， nums[fast] 这个数字已经出现了多少次。如果 nums[fast] 是一个全新的数字（即它与 nums[slow-1] 不同），那么它肯定可以加入。因为一个数字第一次出现，次数为1，小于等于 k 。如果 nums[fast] 与 nums[slow-1] 相同，说明我们正在处理一个重复的数字。这时我们需要检查，这个数字在已处理的数组里已经出现了多少次。但是，我们不需要每次都从头开始计数，因为数组是有序的，相同的数字是连续的。我们只需要检查 nums[fast] 是否与 nums[slow - k] 相同。如果 nums[fast] == nums[slow - k] ，这意味着如果把 nums[fast] 放到 slow 位置，那么在 [slow-k, slow] 这个长度为 k+1 的区间内，就全是 nums[fast] 这个数字了（因为 [slow-k, slow-1] 已经是 k 个相同的数）。这就超过了 k 次的限制。因此，这个 nums[fast] 不能要，我们直接移动 fast 指针，跳过它。如果 nums[fast] != nums[slow - k] ，这意味着即使我们把 nums[fast] 放进去，在已处理的数组末尾， nums[fast] 这个数字的出现次数也严格小于 k 。因此，这个 nums[fast] 是可以加入的。为什么比较 nums[slow - k] 是有效的？因为数组是有序的。如果当前已处理的数组末尾的 k 个元素（即 [slow-k, slow-1] ）都是同一个值 x ，那么 nums[slow - k] 的值就是 x 。如果 nums[fast] 也等于 x ，那么加入它就会导致出现 k+1 次。反之，如果 nums[slow - k] 不是 x ，说明在 [slow-k, slow-1] 这个区间内， x 出现的次数肯定小于 k （因为如果等于 k ，它们必须是连续的 k 个 x ，那么 nums[slow-k] 就一定是 x ）。算法步骤：初始化 slow = 0 , fast = 0 。当 fast 小于数组长度 n 时，执行循环： a. 判断是否可放置：检查 slow 是否小于 k 。如果小于，说明当前合规数组长度还不足以构成一个完整的 k 次重复检查窗口，那么 nums[fast] 可以直接放入（因为无论如何都不会超过 k 次）。 b. 如果 slow >= k ，则需要用上述逻辑判断：检查 nums[fast] 是否等于 nums[slow - k] 。 - 如果相等，说明 nums[fast] 放入会导致重复超过 k 次。我们只移动 fast++ ，跳过它。 - 如果不相等，说明 nums[fast] 可以放入。 c. 对于可以放入的情况（即步骤 a 或步骤 b 中“不相等”的情况）： - 将 nums[fast] 的值赋给 nums[slow] 。 - 然后同时移动 slow 和 fast 指针： slow++ , fast++ 。循环结束后， slow 的值就是新的数组长度。示例推演（nums = [ 1,1,1,2,2,3], k=2）：初始： slow=0 , fast=0 , nums[0]=1 。 slow=0 < k=2 ，直接放入。 nums[0]=1 。 slow=1 , fast=1 。现在： slow=1 , fast=1 , nums[1]=1 。 slow=1 < k=2 ，直接放入。 nums[1]=1 。 slow=2 , fast=2 。现在： slow=2 , fast=2 , nums[2]=1 。 slow=2 >= k=2 ，检查 nums[2] (1) == nums[2-2] (nums[0]=1) ？相等！跳过。只移动 fast=3 。现在： slow=2 , fast=3 , nums[3]=2 。 slow=2 >= k=2 ，检查 nums[3] (2) == nums[2-2] (nums[0]=1) ？不相等！放入。 nums[2]=2 。 slow=3 , fast=4 。现在： slow=3 , fast=4 , nums[4]=2 。 slow=3 >= k=2 ，检查 nums[4] (2) == nums[3-2] (nums[1]=1) ？不相等！放入。 nums[3]=2 。 slow=4 , fast=5 。现在： slow=4 , fast=5 , nums[5]=3 。 slow=4 >= k=2 ，检查 nums[5] (3) == nums[4-2] (nums[2]=2) ？不相等！放入。 nums[4]=3 。 slow=5 , fast=6 。循环结束。新数组为 [1, 1, 2, 2, 3] ，长度为 slow=5 。这个算法的时间复杂度是 O(n)，只需要遍历一次数组。空间复杂度是 O(1)，只使用了常数级别的额外空间。它高效地解决了“最多允许K次重复”的通用问题。