当前位置：首页 > news >正文

LeetCode题解：26.删除有序数组中的重复项【Python题解超详细，双指针法】，知识拓展：原地修改

news 来源：原创 2025/8/3 5:21:04

题目描述

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

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

判题标准:

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

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]。不需要考虑数组中超出新长度后面的元素。

解答

class Solution(object):def removeDuplicates(self, nums):""":type nums: List[int]:rtype: int"""# # 思路一：双指针法一# # 特殊情况的输出# if not nums:#     return 0# # 否则，使用双指针原地修改数组# n = len(nums)# fast = slow = 1# while fast < n:#     if nums[fast] != nums[fast - 1]:#         nums[slow] = nums[fast]#         slow += 1#     fast += 1# # slow就是数组中唯一值的数量# return slow# 双指针法二if not nums:return 0k=0for i in range(1,len(nums)):if nums[i]!=nums[k]:k+=1nums[k]=nums[i]return k+1

双指针法主要思路（以方法二为例）：通过两个指针（k 和 i）在数组上进行遍历以原地去重：k 指向当前存放唯一元素的位置，i 用于遍历数组。如果当前遍历到的元素（nums[i]）与上一个存储的唯一元素（nums[k]）不同，就将其存储到数组的下一个位置（nums[k+1]），并移动指针 k。最终，k+1 即为数组中唯一元素的数量，同时数组的前 k+1 个位置包含了所有唯一元素。

知识拓展：原地修改

或许有些小伙伴在面对题目要求统计唯一值数量时，会感到胸有成竹、信心满满，轻松联想到我们之前文章中详尽阐述过的 set 方法（具体可参见前文LeetCode题解：1.两数之和的知识拓展），进而写下以下代码:

# 获取nums中的唯一值，并将其再次转化为列表
nums=list(set(nums))
# 返回唯一值数量
return len(nums)

但是等到提交的时候却发现这看似简洁、直接而又有效的代码却并未通过断言的测试，那么这是为什么呢？实际上，这道题目的重点并不在于统计唯一值的数量，而是如何原地修改数组，以获取唯一值的情况，那么什么是原地修改呢？使用set的解法为什么不满足条件呢？

原地修改的概念

所谓原地修改，指的是在对象的原内存位置上直接修改其内容，而不是创建一个新的对象。具体表现为：1）对象的 id() （内存地址）在操作前后保持不变；2）修改的是 对象的内部状态，而不是更换对象的引用。并且，在编程中，这种操作可以有效地减少内存使用和提高性能，是许多算法设计的重点要求。

使用set函数的代码之所以出错，原因则在于题目明确要求原地修改数组，而这种方法创建了一个新的列表 list(set(nums))，直接替换了原数组 nums，不符合题目关于 原地操作 的要求。接着，我们再介绍下原地修改其它的相关知识。

原地修改的操作

对列表的操作
- list.sort()：对列表进行排序，直接修改原列表。
- list.append()、list.extend()：在原列表上添加元素。
- list.pop()、list.remove()、del：直接修改原列表，移除元素。
- 切片赋值：nums[:k] = [1, 2, 3]，修改列表的一部分。
- 索引赋值：nums[0] = 10，修改指定位置的值。
对字典的操作
- dict[key] = value：直接修改字典内容。
- dict.update()：合并另一个字典的内容到原字典中。
对集合的操作
- set.add()、set.remove()、set.discard()：修改集合的内容。
- set.update()：将多个元素添加到集合。
对字符串（变更引用，非原地修改）
- Python 中字符串是 不可变对象，任何操作都会创建新字符串对象。

代码示例

# 列表的原地修改
nums = [3, 1, 4]
original_id = id(nums)
nums.sort()
print(id(nums) == original_id)  # True# 字典的原地修改
data = {'a': 1, 'b': 2}
original_id = id(data)
data['c'] = 3
print(id(data) == original_id)  # True# 字符串（非原地修改）
s = "hello"
original_id = id(s)
s = s.upper()  # upper() 创建了一个新字符串
print(id(s) == original_id)  # False

非原地修改的操作

以下操作通常会创建新的对象，导致原地修改要求无法满足：

copy，nums.copy() 创建了原列表的副本，新对象和原对象互不影响。
set，set(nums) 会将列表转换为集合，创建一个全新的对象。
sorted，sorted(nums) 返回一个新的排序列表，原数组不变。
切片创建新列表，nums[:] 或 nums[1:] 会创建原数组的副本。

如何检测是否原地修改

可以通过 id() 函数来验证：

nums = [1, 2, 3]
original_id = id(nums)# 原地修改
nums.sort()
print(id(nums) == original_id)  # True# 非原地修改
nums = sorted(nums)
print(id(nums) == original_id)  # False

原地修改的意义

减少空间开销：原地修改不会占用额外的内存空间，尤其对于大规模数据处理非常重要。
提高性能：避免创建新的对象可以减少不必要的计算和复制操作。

常见的原地修改场景

排序问题：
- 使用 list.sort() 而不是 sorted()，直接在原列表中进行排序。
去重问题：
- 使用双指针法在数组中删除重复项，直接修改原数组。
数据清洗：
- 在数据处理中，直接删除不需要的数据，而不是创建新副本。

感谢阅读，希望对你有所帮助~