确定Python列表是否相同95%？

Question

这个问题询问如何确定列表中的每个元素是否相同.我如何以合理有效的方式确定列表中95%的元素是否相同？例如:

>>> ninety_five_same([1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
True
>>> ninety_five_same([1,1,1,1,1,1,2,1]) # only 80% the same
False

这需要有些效率,因为列表可能非常大.

Answer 1

>>> from collections import Counter
>>> lst = [1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
>>> _, freq = Counter(lst).most_common(1)[0]
>>> len(lst)*.95 <= freq
True

Answer 2

实际上,对于类似的问题,有一个简单的线性解决方案,只有50%的约束而不是95%.检查这个问题,它只是几行代码.

它也适用于你,最后你只检查所选元素是否满足95%的阈值,而不是50%.(虽然,正如Thilo所说,如果currentCount >= n*0.95已经没有必要的话.)

我还将从st0le的回答中发布Python代码,向大家展示它有多难.

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1

如果您正在寻找解释,我认为Nabb已经得到了最好的解释.

Answer 3

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freqsort = sorted(freq.itervalues())
    return freqsort[-1] >= .95 * sum(freqsort)

假设完美的哈希表性能和良好的排序算法,这在O(n + m lg m)中运行,其中m是不同项的数量.O(n lg n)最坏的情况.

编辑:这是一个O(n + m),单通道版本(假设m << n):

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freq = freq.values()
    return max(freq) >= .95 * sum(freq)

内存使用是O(m).max并且sum可以用单个循环代替.