如何快速找到数组中未成对的元素？
如何快速找到数组中未成对的元素？
提问于 2019-06-21 03:37:14
我正在练习Codility中的一些问题。然而，每次我运行这些问题时，我得到的性能(运行时)得分都非常低(25%)。你能帮助我知道如何提高我的代码，以便获得更好的分数吗？
问题是：
编写一个函数：
def solution(A)在给定由满足上述条件的N个整数组成的数组A的情况下，返回未成对元素的值。
例如，给定数组A，使得：
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9该函数应返回7，如上面的示例所述。
和我的相同代码是：
def solution(A):
# write your code in Python 3.6
lis=[i for i in A if A.count(i) ==1]
return lis[0]输出：
medium2 "medium random test n=100,003
✘TIMEOUT ERROR Killed。硬限制已达到: 6.000秒“
回答 3
Stack Overflow用户
回答已采纳
发布于 2019-06-21 03:40:14
这是因为list.count每次都会搜索整个列表，它是O( N ) *N或N**2。你可以使用collections.Counter来计算一个项目出现的次数，或者在一次遍历中，查找次数是O(1)，因为它是一个字典：
from collections import Counter
def solution(A):
c = Counter(A)
# this will iterate over all the key/value pairs
# which is at worst N elements long
return [k for k, v in c.items() if v==1]要显示速度的提高，请执行以下操作：
python -m timeit -s "from random import randint; A = [randint(0,500) for i in range(10000)]" "x = [a for a in A if A.count(a)==1]"
10 loops, best of 3: 957 msec per loop
python -m timeit -s "from random import randint; from collections import Counter; A = [randint(0,500) for i in range(10000)]; c = Counter(A)" "x = [s for s, v in c.items() if v==1]"
10000 loops, best of 3: 20.1 usec per loop因此，尽管每次运行的时间并不完全相同，但我认为平均情况不言而喻。
Stack Overflow用户
发布于 2019-06-21 03:55:58
与使用collections.Counter的版本相比，使用itertools.groupby()的版本的性能大约高出3倍
import collections
from itertools import groupby
import timeit
l = [9, 3, 9, 3, 9, 7, 9]
def fn1(lst):
return [v for v, g in groupby(sorted(lst)) if len([*g]) == 1]
def fn2(lst):
k = collections.Counter(lst)
return [i for i in k if k[i] == 1]
print(timeit.timeit(lambda: fn1(l), number=100_000, globals=globals()) )
print(timeit.timeit(lambda: fn2(l), number=100_000, globals=globals()) )打印：
0.11646193999331445
0.33489679799822625Stack Overflow用户
发布于 2019-06-21 03:45:19
尝试以下操作：
import collections
k = collections.Counter(A)
return [ i for i in k if k[i] == 1]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56692796
复制相关文章
相似问题