【Day25】26.删除有序数组中的重复项 80.删除有序数组中的重复项II

文章目录

• 26.删除有序数组中的重复项
• 题目：
• 思路：
• • 复杂度
• 代码实现（Go）：
• 80.删除有序数组中的重复项II
• 题目：
• 思路：
• • 流程
  • 复杂度
• 代码实现（Go）
• • 对比
  • • k = 1（每个元素最多出现 1 次）
    • k = 2（每个元素最多出现 2 次）

26.删除有序数组中的重复项

题目：

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k – 1 之后的剩余元素可以忽略。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组 int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } 如果所有断言都通过，那么您的题解将被 通过。

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

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

提示：

1 <= nums.length <= 3 * 10^4 -100 <= nums[i] <= 100 nums 已按 非递减 顺序排列。

思路：

这题是 有序数组原地去重，标准的 双指针 问题。

因为 nums 已经是 非递减排序 的：

• 重复元素一定是连续的
• 只要把每一段重复里的 第一个元素保留下来 即可

双指针定义

• slow：指向 下一个可以写入的位置
• fast：从前往后扫描数组

[0 .. slow-1] 始终表示 已经去重后的最终结果

核心逻辑

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)（原地修改）

代码实现（Go）：

package main

import "fmt"

func removeDuplicates(nums []int) int {
// 特殊情况：空数组
if len(nums) == 0 {
return 0
}

// slow 指向下一个可写入的位置
slow := 1

// fast 用来遍历数组
for fast := 1; fast < len(nums); fast++ {
// 只要和结果区最后一个元素不同，就可以写入
if nums[fast] != nums[slow–1] {
nums[slow] = nums[fast]
slow++
}
}

// 去重后的长度
return slow
}

func main() {
nums1 := []int{1, 1, 2}
k1 := removeDuplicates(nums1)
fmt.Println("k =", k1)
fmt.Println("nums =", nums1[:k1])

nums2 := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
k2 := removeDuplicates(nums2)
fmt.Println("k =", k2)
fmt.Println("nums =", nums2[:k2])
}

80.删除有序数组中的重复项II

题目：

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

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

说明：

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

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

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

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

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

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

示例 2： 输入：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 * 10^4 -10^4 <= nums[i] <= 10^4 nums 已按升序排列

思路：

因为数组是 升序 的，相同元素一定是连续的。

核心约束

每个数字最多保留 2 个

双指针设计

• slow：指向 下一个可写入的位置（结果区长度）
• fast：遍历整个数组

判断条件

从第 3 个元素开始考虑：

如果 nums[fast] != nums[slow-2]，就可以保留

原因：

• slow-2 位置的元素是当前结果区 最早保留的那个元素
• 如果 fast 再等于 nums[slow-2]，说明这是 第 3 次出现 → 丢掉
• 如果不等，说明是新数或还在允许次数范围 → 可以写入

流程

slow：下一个可以写入的位置 slow-2：当前结果区允许保留次数的边界元素

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)（原地修改）

代码实现（Go）

package main

import "fmt"

func removeDuplicates(nums []int) int {
n := len(nums)
if n <= 2 {
return n
}

slow := 2 // 下一个可写位置
for fast := 2; fast < n; fast++ {
// 核心判断：最多保留 2 次
if nums[fast] != nums[slow–2] {
nums[slow] = nums[fast]
slow++
}
}
return slow
}

func main() {
nums1 := []int{1, 1, 1, 2, 2, 3}
k1 := removeDuplicates(nums1)
fmt.Println("k =", k1)
fmt.Println("nums =", nums1[:k1])

nums2 := []int{0, 0, 1, 1, 1, 1, 2, 3, 3}
k2 := removeDuplicates(nums2)
fmt.Println("k =", k2)
fmt.Println("nums =", nums2[:k2])
}

对比

本质：判断“当前元素会不会超过允许次数” slow 初始 = k（允许保留次数），判断条件使用 slow-k 就可以控制每段重复元素不会超过 k 次

如 nums = [0, 1, 1, 1]

k = 1（每个元素最多出现 1 次）

最终结果数组 [0,1] ✅

k = 2（每个元素最多出现 2 次）

最终结果数组 [0,1,1] ✅

• slow 总是指 下一个可写位置
• slow-1 或 slow-2（取决于 k）是结果区允许保留次数的最左边界，也就是 当前段重复元素已经保留的最早位置。
• 因为要这样用左边界比较 所以最初才要留够对应的k的数量。