Python3排序数组去重算法：三种实现方案与复杂度分析

不晚

发布时间：2026-10-13| 5人浏览过

原创

本文深入解析Python3中从排序数组删除重复项的三种实现方式。重点对比利用set()快速去重、双指针法原地修改以及调用remove()方法的效率差异。所有方案均遵循O(1)额外空间限制，通过具体代码示例展示如何返回新长度并优化数组内容，帮助开发者根据实际场景选择最优解。

Python3排序数组去重算法概述

本文详细介绍在Python3环境下，如何高效实现从已排序数组中移除重复元素的算法逻辑。

题目要求：给定一个已排序的数组，需在原地执行操作以删除重复出现的元素，确保每个元素仅保留一个实例，并最终返回处理后数组的新长度。

约束条件：禁止使用额外的数组空间，必须在原地修改输入数组的前提下，且仅使用O(1)的额外空间来完成该任务。

方案一：利用set()快速去重

方案一：利用set()快速剔除重复元素。此方法执行效率最高。


# -*- coding:utf-8 -*-
#! python3
def removeDuclicates(nums):
  nums[:] = sorted(set(nums))
  return len(nums)
#测试
arr1 = [1,1,2,3,4,5,5,6]
print(removeDuclicates(arr1))

运行结果：

6

方案二：双指针法实现

方案二：采用双指针法。执行效率次之。


# -*- coding:utf-8 -*-
#! python3
def removeDuplicates(nums):
  if not nums:
    return 0
  j = 0
  for i in range(1, len(nums)):
    if nums[j] != nums[i]:
      j += 1
      nums[j] = nums[i]
  return j + 1
#测试
arr1 = [1,1,2,3,4,5,5,6]
print(removeDuplicates(arr1))

运行结果：

6

方案三：调用remove()方法

方案三：利用remove()方法。执行效率次之。


# -*- coding:utf-8 -*-
#! python3
def removeDuplicates(nums):
  i = 0
  while i < len(nums) - 1:
    if nums[i] == nums[i + 1]:
      nums.remove(nums[i])
    else:
      i += 1
  return len(nums)
#测试
arr1 = [1,1,2,3,4,5,5,6]
print(removeDuplicates(arr1))

运行结果：