如何优化数组重复项查找？适配大数据量的高效实现方案问询

原代码用两层嵌套循环检查重复，时间复杂度是O(n²)，大数据量下会严重拖慢速度——比如当数组有10000个元素时，要做近5000万次比对，效率极低。下面是几种针对大数据量的优化方案：

方案一：利用集合（Set）快速查重 #

集合的核心特性是不允许重复元素，而且插入、查找的平均时间复杂度都是O(1)，整体时间复杂度可以降到O(n)，是大数据量下最快的方案。

实现思路 #

• 遍历数组，把每个元素加入集合
• 如果某个元素加入前已经在集合里，直接返回True（找到重复）
• 遍历结束后没找到重复，返回False

或者更简洁的写法：直接比较原数组长度和转成集合后的长度，长度不等就说明有重复。

代码示例 #

import random

nums = [random.randint(-100, 100) for _ in range(10)]
print(nums)

# 简洁版
has_duplicate = len(set(nums)) != len(nums)
print(has_duplicate)

# 提前终止版（找到重复就立刻停止，更省时间）
seen = set()
has_duplicate = False
for num in nums:
    if num in seen:
        has_duplicate = True
        break
    seen.add(num)
print(has_duplicate)

方案二：排序后检查相邻元素 #

先对数组排序，排序的时间复杂度是O(n log n)，之后只需要遍历一次数组，检查相邻元素是否相等即可，整体时间复杂度比嵌套循环低很多，而且不需要额外的空间（如果允许修改原数组）。

实现思路 #

• 对原数组进行原地排序
• 遍历数组，比较当前元素和下一个元素
• 发现相等就返回True，遍历结束返回False

代码示例 #

import random

nums = [random.randint(-100, 100) for _ in range(10)]
print(nums)

nums.sort()
has_duplicate = False
for i in range(len(nums)-1):
    if nums[i] == nums[i+1]:
        has_duplicate = True
        break
print(has_duplicate)

方案对比 #

• 集合方案：速度最快，适合对时间要求高的场景，但需要额外的空间存储集合，空间复杂度O(n)
• 排序方案：不需要额外空间（原地排序），但速度比集合稍慢，适合内存紧张的场景

输入输出示例验证：

输入：nums = [1,2,3,1] → 输出：true
输入：nums = [1,2,3,4] → 输出：false
输入：nums = [1,1,1,3,3,4,3,2,4,2] → 输出：true

以上两种方案都能正确处理这些示例，且在大数据量下的性能远优于原代码。

内容的提问来源于stack exchange，提问作者EF1M