Codewars查找数组唯一元素遇执行超时，求Python代码优化方案

优化方案 #

你的代码超时核心问题是**arr.count(n)的效率太低**：每次调用count都会完整遍历一次数组，假设数组长度是n，你的代码整体时间复杂度是O(n²)，面对大数组时必然超时。下面是几个高效的解决办法：

方案1：统计元素出现次数（直观易懂）

用字典或collections.Counter一次性统计所有元素的出现次数，再找出次数为1的元素。统计过程只需要一次遍历，效率很高：

from collections import Counter

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

如果不想用内置模块，也可以手动实现统计：

def find_uniq(arr):
    count = {}
    for num in arr:
        count[num] = count.get(num, 0) + 1
    for num, freq in count.items():
        if freq == 1:
            return num

方案2：利用排序特性（无需额外空间）

数组排序后，唯一的元素要么在开头，要么在结尾（因为其他元素都相同）：

def find_uniq(arr):
    arr.sort()
    # 第一个元素和第二个不同，说明第一个是唯一值
    if arr[0] != arr[1]:
        return arr[0]
    # 否则唯一值一定在最后
    return arr[-1]

这个方法的时间复杂度由排序决定（O(n log n)），空间开销很小（Python的sort是原地排序）。

方案3：快速定位基准值（最高效）

题目保证数组至少有3个元素，且只有一个唯一值，我们可以通过前三个元素快速确定重复的基准值，再遍历找到唯一值：

def find_uniq(arr):
    # 确定重复的基准值
    if arr[0] == arr[1]:
        base = arr[0]
    elif arr[0] == arr[2]:
        base = arr[0]
    else:
        # 此时arr[1]和arr[2]必然相同
        base = arr[1]
    # 遍历找到第一个不等于基准值的元素
    for num in arr:
        if num != base:
            return num

这个方法只需要一次遍历，时间复杂度O(n)，没有额外空间开销，是效率最高的方案之一。

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