作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
问题描述
给你一个升序排列的数组 nums，你需要原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1, 2。不需要考虑数组中超出新长度后面的元素。
双指针法
本题目要求在原数组上操作，不使用额外空间，这提示我们可以使用双指针技术来解决问题。具体策略如下：
- 设置两个指针：一个快指针
fast和一个慢指针slow。快指针用于遍历数组，慢指针用于指向处理好的数组的最后一个位置。 - 遍历数组：快指针从第二个元素开始遍历，如果发现与慢指针指向的元素不同，则将慢指针向前移动一位，并将快指针的元素复制到慢指针的位置。
- 更新数组：遍历完成后，数组前
slow + 1个元素即为去重后的数组。
算法分析
- 时间复杂度：O(n)，其中
n是数组的长度。快指针会遍历一次数组。 - 空间复杂度：O(1)，只使用了两个指针作为额外空间。
代码实现
def removeDuplicates(nums): if not nums: return 0 slow = 0 for fast in range(1, len(nums)): if nums[fast] != nums[slow]: slow += 1 nums[slow] = nums[fast] return slow + 1 # 调用函数示例 nums = [1, 1, 2] new_length = removeDuplicates(nums) print("New length:", new_length) print("Updated array:", nums[:new_length])
输出
New length: 2 Updated array: [1, 2]
图解双指针
我们将详细图解双指针法处理“删除排序数组中的重复项”的过程。下面是每一步的说明和相应的ASCII图表展示：
初始状态
nums = [1, 1, 2] ^ | slow (初始化在0) ^ | fast (初始化在1)
- slow 指针指向数组的第一个元素。
- fast 指针开始从数组的第二个元素进行遍历。
迭代过程
Step 1: fast = 1, nums[fast] = 1
nums[fast] == nums[slow]，所以 `fast` 指针向前移动，`slow` 指针不动。
nums = [1, 1, 2] ^ ^ | | slow fast - nums[fast] == nums[slow]，所以 `fast` 指针向前移动，`slow` 指针不动。
Step 2: fast = 2, nums[fast] = 2
nums = [1, 1, 2] ^ ^ | | slow fast - nums[fast] != nums[slow]，这意味着我们找到了一个新的不重复元素。 - 将 `slow` 前移一位，然后将 `fast` 的值复制到 `slow` 的位置。
复制后的数组状态：
nums = [1, 2, 2] ^ ^ | | slow fast - `slow` 指针指向最后一个无重复的元素。 - `fast` 指针继续向前探索。
最终结果
经过上述步骤，数组中 slow 指针前（包含 slow 指针指向的位置）的元素 [1, 2] 是去重后的结果。
新的数组有效长度为 slow + 1，即 2。
Final Array = [1, 2] Length = 2
其他方法（参考）
1. 直接修改数组法
虽然这看似与双指针方法相似，实质上它更直接地修改数组，不显式分快慢指针，更注重操作的逻辑清晰：
def removeDuplicates(nums): if not nums: return 0 # 新数组的索引 new_index = 0 # 遍历数组 for i in range(1, len(nums)): if nums[i] != nums[new_index]: new_index += 1 nums[new_index] = nums[i] return new_index + 1
2. 使用集合辅助
这种方法虽然使用了额外的空间，违背了题目要求的O(1)额外空间的条件，但在某些情况下可以为问题提供新的视角：
def removeDuplicates(nums): # 用集合存储已经看到的元素 seen = set() write_index = 0 for num in nums: if num not in seen: nums[write_index] = num write_index += 1 seen.add(num) return write_index
3. 排序后去重
对于非排序数组，首先进行排序，然后再去重。但对于已经排序的数组，这个方法和直接去重没有区别，仅提供一个思路上的变通：
def removeDuplicates(nums): if not nums: return 0 nums.sort() # 对于已排序数组，这一步是多余的 new_index = 0 for i in range(1, len(nums)): if nums[i] != nums[new_index]: new_index += 1 nums[new_index] = nums[i] return new_index + 1
4. Python特有方法
利用Python语言特性简化代码，但这种方法通常不适用于面试中，因为它隐藏了处理的细节：
def removeDuplicates(nums): nums[:] = sorted(set(nums)) return len(nums)
结论
虽然有多种方法可以解决这一问题，但双指针法因其空间复杂度低（O(1)），并且直接在输入数组上进行操作的特性，通常是最优解。其他方法如使用集合虽然易于理解，但使用了额外空间，不满足题目的空间复杂度要求。
欢迎关注微信公众号 数据分析螺丝钉
