Codewars‘寻找唯一数字’问题超时，求教性能优化及set()高效原理

问题描述 #

存在一个数组，其中除一个数字外其余所有数字均相同，请找出这个唯一数字。示例：

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

题目保证数组至少包含3个元素，测试用例包含超大数组，需重点考虑性能。

现有代码与性能问题 #

你编写的代码如下：

def find_uniq(arr):
    for i in arr:
        if arr.count(i)==1:
            return i

这段代码超时的核心原因是：每次调用arr.count(i)都会完整遍历一遍数组统计次数。假设数组长度为n，最坏情况下要执行n次全数组遍历，时间复杂度为O(n²)，在超大数组下会因为重复遍历导致耗时剧增，触发超时。

性能优化方案 #

方案1：利用集合去重减少统计次数 #

def find_uniq(arr):
    unique_nums = set(arr)
    # 集合里最多只有两个元素，仅需统计两次
    for num in unique_nums:
        if arr.count(num) == 1:
            return num

方案2：用字典统计频率（一次遍历完成统计） #

from collections import defaultdict

def find_uniq(arr):
    freq = defaultdict(int)
    for num in arr:
        freq[num] += 1
    # 字典最多两个键值对，直接查找次数为1的元素
    for num, count in freq.items():
        if count == 1:
            return num

方案3：基于多数元素判断（最优性能，无额外空间开销） #

def find_uniq(arr):
    # 从数组前3个元素确定多数元素（题目保证除一个外其余都相同）
    if arr[0] == arr[1]:
        majority = arr[0]
    elif arr[0] == arr[2]:
        majority = arr[0]
    else:
        majority = arr[1]
    # 遍历数组找到第一个不等于多数元素的数
    for num in arr:
        if num != majority:
            return num

为什么set()能提升性能？ #

原数组中只有两种不同的元素，set(arr)会自动去重，得到一个最多包含2个元素的集合：

• 原代码需要对数组中每个元素都执行一次count（n次全数组遍历），时间复杂度O(n²)；
• 用set后，仅需对集合里的2个元素各执行一次count，总共只需要2次数组遍历，时间复杂度直接降为O(n)，性能提升非常明显。

另外，set的底层是哈希表，查找元素的时间复杂度为O(1)，但这里核心优化点是通过去重减少了不必要的统计次数，从而大幅降低总耗时。

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