Remove Duplicates from Sorted Array
你会得到一个按非递减顺序排序的整数数组 nums，因此相等的值会相邻排列。按出现顺序返回 nums 中的不同值，每个值只返回一次。例如，[2, 2, 5] 会得到 [2, 5]。
函数
- numsinteger-array
- 按非递减顺序排列的整数
- 返回值integer-array
- nums 中按升序排列的不同值
约束条件
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104nums已按非递减顺序排序。
示例
- 输入
- nums = [1, 1, 2, 3, 3, 3]
- 输出
- [1, 2, 3]
- 解释
1出现了两次，3出现了三次。每个数只保留一个，就得到[1, 2, 3]。
- 输入
- nums = [-2, 0, 0, 5]
- 输出
- [-2, 0, 5]
- 解释
- 只有
0会重复。负值的处理方式相同，所以答案是[-2, 0, 5]。
- 输入
- nums = [7, 7, 7]
- 输出
- [7]
- 解释
- 所有值都是
7，所以只剩下一个7。
进阶
你能通过原地重写 nums，而不是构建第二个数组，使用 O(1) 的额外内存来完成吗？
提示
逐个打开提示，每个都会多透露一点。
由于
nums已排序，同一个值的所有副本会连在一起。怎样才能在不记住你见过的每个值的情况下，判断某个值是不是它所在连续段的第一个值？当一个值与上一个保留的值不同时，就会开始一个新的连续段。因此，你只需与一个值进行比较，并在处理过程中从数组的开头开始覆盖。
保留一个写入索引
k，初始值为 1，因为nums[0]始终会保留。读取后面的每个值；如果它与nums[k-1]不同，就将它复制到nums[k]，并将k加 1。返回前k个值。
题解
在未排序的数组中，你必须记住见过的每个值。排序会把同一个值的所有副本放在一起，因此，当一个值与上次保留的值不同时，它就是新值。用一个读取索引和一个写入索引遍历一遍，就能原地完成这项工作。
在哈希集合中记录已见过的值
思路
遍历 nums，并用一个集合记录答案中已有的值。第一次遇到某个值时，将它追加到答案中；之后再遇到时就跳过，这样每个值只出现一次，并按遇到的顺序排列。这种方法不会使用排序顺序，而且适用于任何数组。
集合查找的平均时间复杂度是 O(1)，所以遍历的时间复杂度是 O(n)，但集合和答案各自都可能存储 n 个值：额外空间复杂度为 O(n)。在 C 中，可以用一个标记数组替代集合，标记数组覆盖 2 × 10^4 + 1 个可能的值。
算法
- 创建一个空集合
seen和一个空列表result。 - 对于
nums中的每个值，检查它是否在seen中。 - 如果不在，就将它添加到
seen，并将它追加到result。 - 返回
result。
def removeDuplicates(nums):
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
return result使用写入指针原地压缩
思路
写入索引 k 标记保留部分的末尾：到目前为止，nums[0] 到 nums[k-1] 始终存放已找到的不同值，因此 nums[k-1] 是最后一个保留的值。读取索引 i 会遍历每个值。与 nums[k-1] 相同的值，是你已经保留的连续段中的另一个副本；不同的值则开始一个新的连续段，并写入 nums[k]。
对于 [1, 1, 2, 3, 3, 3]，i = 1 会跳过第二个 1，i = 2 会将 2 写入索引 1，i = 3 会将 3 写入索引 2，最后两个 3 会被跳过。前三个位置读出的内容是 [1, 2, 3]。
由于 k 永远不会超过 i，写入操作不会覆盖你尚未读取的值。整个过程的时间复杂度为 O(n)，额外空间只需存放两个整数。
算法
- 将
k = 1：始终保留nums[0]。 - 让
i从 1 循环到最后一个索引。 - 如果
nums[i]与nums[k-1]不同，就将nums[k]设为nums[i]，并将k加 1。 - 返回
nums的前k个值。
def removeDuplicates(nums):
# nums[0:k] holds the distinct values found so far, in order.
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return nums[:k]
易错点和边界情况
- 当
i遍历到最后一个索引时，比较nums[i]和nums[i+1]。最后一次比较会读取数组末尾之后的位置。 - 将
k从 0 开始。这样，第一个值会与nums[-1]比较，这会导致索引越界，或者在 Python 中访问最后一个元素。 - 返回整个数组，而不是前
k个值。末尾仍保留着旧值，所以[1, 1, 2]会变成[1, 2, 2]。 - 通过遍历哈希集合来构造答案。大多数哈希集合不保留顺序，因此值的顺序可能会打乱。
- 在 Lua 和 R 中，数组从 1 开始。保留的部分是
nums[1]到nums[k]，比较时要与nums[k]比较。
常见问题3
从排序数组中删除重复项的时间复杂度是多少？
写指针解法只读取每个值一次，因此运行时间为 O(n)。除了返回的值，它只使用 O(1) 的额外空间：两个索引。
为什么数组需要排序？
排序会将每个值的所有副本放在同一段中，因此只需与上一个保留的值比较即可。在未排序的数组中，副本可能出现在任何位置，因此你需要用哈希集合记录所有见过的值，这会额外占用 O(n) 的空间。
如何允许每个值最多出现两次？
与保留部分中前两个位置的值比较，而不是前一个：当 k < 2 或 nums[i] 与 nums[k-2] 不同时，复制 nums[i]。如果它等于 nums[k-2]，保留部分的末尾已经有两个相同的值。用 nums[k-m] 可以用同样的思路保留最多 m 个副本。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def removeDuplicates(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [1, 1, 2, 3, 3, 3]
预期输出
[1, 2, 3]