确定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

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 可以通过一个循环来替代。

Answer 2

当然可以！请看下面的内容：

在编程中，有时候我们需要让程序做一些事情，比如计算、显示信息或者处理数据。为了实现这些功能，我们通常会写一些代码。代码就像是给计算机下达的指令，告诉它该做什么。

在这个过程中，我们可能会遇到一些问题，比如代码运行不正常或者出现错误。这时候，我们就需要去查找问题的原因，看看哪里出了错。这个过程叫做调试。

调试就像是侦探破案，我们需要仔细观察，找出问题的线索，然后一步步解决它。通过调试，我们可以让程序更好地工作，完成我们想要的任务。

希望这些解释能帮助你更好地理解编程的基本概念！

>>> 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 3

其实，对于类似的问题，有一个简单的线性解决方案，只需要满足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提供的是最好的解释。