算法优化 - 在列表中查找唯一编号 [英] Algorithm optimization - Find the unique number in a list

问题描述

目标是在包含相同数字的数组中找到唯一的数字，除了一个.速度至关重要，因为数组可能很大.我下面的代码适用于较小的数组，但对于大型数组会超时.如何改进算法?请参阅下面的输入/输出示例:

The goal is to find the unique number in an array which contains identical numbers except one. Speed is of the essence as arrays can be huge. My code below works for smaller arrays but times out for large arrays. How to improve the algo? See input / output example below:

输入 = [1, 1, 1, 1, 2, 1, 1, 1, 1]输出 = 2

Input = [1, 1, 1, 1, 2, 1, 1, 1, 1] Output = 2

def find_uniq(arr):

    result = [x for x in arr if arr.count(x) ==1]
    return result[0]

推荐答案

您当前的解决方案是二次方！

您可以将其降低为线性，使用 collections.Counter 与 next 相关联(当您不想只构建整个列表时非常方便)扔掉).计数是预先计算的，然后返回找到的第一个唯一值.

You can bring this down to linear, using collections.Counter in association with next (very handy when you don't want the entire list being built only to be thrown away). The counts are precomputed and then the first unique value found is returned.

from collections import Counter

def find_uniq(arr):
    c = Counter(arr)
    return next(x for x in arr if c[x] == 1)

next 在这里大放异彩，因为目标是返回找到的第一个唯一值.next 使用生成器，只返回第一项(进一步计算停止).

next shines here because the goal is to return the first unique value found. next works with a generator, and only the first item is returned (further computation halts).

这篇关于算法优化 - 在列表中查找唯一编号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！