查找列表中唯一独特值的Codewars题目解法超时问题求助

超时原因分析 #

你当前的解法时间复杂度为O(n²)，arr.count(element)方法每次调用都会完整遍历一次数组统计元素出现次数，叠加外层的遍历逻辑，当测试用例的数组元素量级很大时，执行耗时会远超阈值。

优化解法 #

方案1：通用频率统计（适用性广） #

使用Python标准库collections.Counter仅需遍历数组1次即可完成所有元素的频率统计，总时间复杂度为O(n)，可以轻松应对大数组场景：

from collections import Counter

def find_uniq(arr):
    freq_counter = Counter(arr)
    for num, count in freq_counter.items():
        if count == 1:
            return num

方案2：针对题目特性的极致优化 #

该题规则为数组中仅存在两种不同数值，其中一种仅出现1次，另一种占据剩余所有位置。利用这个特性我们可以先快速定位到重复的通用值，再遍历一次找唯一的特殊值即可，常数复杂度更低，执行速度更快：

def find_uniq(arr):
    # 先确定占多数的通用值
    first, second = arr[0], arr[1]
    if first == second:
        common_val = first
    else:
        # 前两个值不同时，看第三个值和谁一致就能确定通用值
        common_val = first if arr[2] == first else second
    # 遍历找到唯一的特殊值
    for num in arr:
        if num != common_val:
            return num

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