🎬 HoRain云小助手：个人主页

 🔥 个人专栏: 《Linux 系列教程》《c语言教程》

⛺️生活的理想，就是为了理想的生活!

---

⛳️ 推荐

前些天发现了一个超棒的服务器购买网站，性价比超高，大内存超划算！忍不住分享一下给大家。点击跳转到网站。

专栏介绍

专栏名称	专栏介绍
《C语言》	本专栏主要撰写C干货内容和编程技巧，让大家从底层了解C，把更多的知识由抽象到简单通俗易懂。
《网络协议》	本专栏主要是注重从底层来给大家一步步剖析网络协议的奥秘，一起解密网络协议在运行中协议的基本运行机制！
《docker容器精解篇》	全面深入解析 docker 容器，从基础到进阶，涵盖原理、操作、实践案例，助您精通 docker。
《linux系列》	本专栏主要撰写Linux干货内容，从基础到进阶，知识由抽象到简单通俗易懂，帮你从新手小白到扫地僧。
《python 系列》	本专栏着重撰写Python相关的干货内容与编程技巧，助力大家从底层去认识Python，将更多复杂的知识由抽象转化为简单易懂的内容。
《试题库》	本专栏主要是发布一些考试和练习题库（涵盖软考、HCIE、HRCE、CCNA等）

目录

⛳️ 推荐

专栏介绍

🔍 方法一：双指针（快慢指针）

​​思路​​

​​代码实现​​

​​复杂度分析​​

⚠️ 其他方法及注意事项

💎 总结

---

删除有序数组中的重复项是一个常见的算法问题，其核心在于​​原地修改数组​​并使用 ​​O(1) 额外空间​​。由于数组是有序的，重复元素会连续出现，这为高效解决问题提供了条件。

以下是解决该问题的几种Python方法，我将为你详细解释其中最优雅和高效的双指针法，并提供代码示例。

🔍 方法一：双指针（快慢指针）

这是解决此类问题的最常见且高效的方法。

​​思路​​

1. ​​初始化指针​​：设置一个慢指针 slow，其初始位置为0（或1，取决于实现），用于指向下一个唯一元素应存放的位置；一个快指针 fast，用于遍历数组。

2. ​​遍历数组​​：快指针 fast从头到尾遍历数组。

3. ​​发现不重复元素​​：当 nums[fast]不等于 nums[slow]（或 nums[slow-1]，取决于 slow的初始位置）时，说明遇到了新的唯一元素。将 slow指针后移一位，并将 nums[fast]的值赋给 nums[slow]。

4. ​​返回长度​​：遍历结束后，slow指针的位置（或 slow+1）即为新数组的长度。

​​代码实现​​

def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:  # 处理空数组的情况
        return 0
        
    slow = 1  # 慢指针，从索引1开始（因为索引0的元素肯定是唯一的）
    n = len(nums)
    
    for fast in range(1, n):  # 快指针从索引1开始遍历
        if nums[fast] != nums[fast - 1]:  # 当前元素与前一个元素比较
            nums[slow] = nums[fast]  # 将新的唯一元素赋值给slow指针的位置
            slow += 1  # 慢指针后移
    return slow  # 返回新数组的长度

# 示例用法
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
length = removeDuplicates(nums)
print(f"新数组长度: {length}")
print(f"修改后的数组前{length}个元素: {nums[:length]}")
# 输出:
# 新数组长度: 5
# 修改后的数组前5个元素: [0, 1, 2, 3, 4]

另一种常见的双指针写法，slow从0开始：

def removeDuplicates(nums):
    if not nums:
        return 0
    j = 0  # 慢指针
    for i in range(1, len(nums)):  # i 是快指针
        if nums[i] != nums[j]:
            j += 1
            nums[j] = nums[i]
    return j + 1

​​复杂度分析​​

• ​​时间复杂度​​：O(n)，其中 n 是数组的长度。快指针 fast只需遍历数组一次。

• ​​空间复杂度​​：O(1)。我们只使用了常数个额外变量（slow和 fast或 i和 j）。

⚠️ 其他方法及注意事项

1. ​​使用 pop方法​​：某些方法在遍历过程中遇到重复元素时使用 pop来移除。​​一般不推荐​​，因为 pop操作的时间复杂度为 O(n)，导致总体时间复杂度升至 O(n²)，尤其在数组较大时效率较低。

2. ​​使用 count方法​​：在循环中使用 nums.count(nums[i])判断重复并删除。​​极其不推荐​​，count方法本身是 O(n) 操作，会使算法的时间复杂度变得非常高（例如 O(n²) 或更糟）。

3. ​​哈希集合去重​​：虽然 set可用于去重，但​​无法满足“原地修改”和“O(1)空间”的要求​​，因为它需要额外空间存储集合。

💎 总结

对于删除有序数组中的重复项问题，​​双指针法是最优解​​。它高效地利用了数组已排序的特性，通过一次遍历和原地交换，以 O(n) 的时间复杂度和 O(1) 的空间复杂度完成任务。

方法	时间复杂度	空间复杂度	推荐度
​​双指针​​	​​O(n)​​	​​O(1)​​	★★★★★
使用 pop	O(n²)	O(1)	★☆☆☆☆
使用 count	O(n²) (或更糟)	O(1)	☆☆☆☆☆

希望这些解释和代码示例能帮助你更好地理解如何解决这个问题。如果你有兴趣，可以尝试一下LeetCode的类似题目（如第80题，允许元素最多出现两次）来巩固这个技巧。

❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙