以最佳时间复杂度获取列表中最常出现的5个元素

Question

我试图从列表中找出5个最常出现的元素及其出现次数。我用一个时间复杂度为O（5*n*n）的解决方案解决了这个问题。你知道吗

有没有时间复杂度更好的最优解？你知道吗

输入示例：

[['16.37.123.153','119.222.456.130','38673','161','17','62','4646']
 ['16.37.456.153','119.222.123.112','56388','161','17','62','4646']..]

输出示例：

MostOccurrentElements = [['16.37.123.153','119.222.456.130','38673','161','17','62','4646']..]
Counter = [134, ..]

MostOccurrentElements列表的第一个元素与计数器列表的第一个元素匹配。你知道吗

Answer 1

您可以使用heapq.nlargest方法来获取O（nlog（t））时间复杂度中最常出现的5个项，其中n是要获取的项的数量，t是要获取的最大项的数量。collections.Counter可以在O（n）时间内获得每个不同项值的计数，因此总体而言，下面的代码可以在O（n log（t）的平均值中找到5个最常出现的项：

from collections import Counter
import heapq
from operator import itemgetter
l = [1,1,2,3,3,3,3,4,4,4,4,5,5,6,6,6,7]
print(heapq.nlargest(5, Counter(l).items(), key=itemgetter(1)))

这将输出：

[(3, 4), (4, 4), (6, 3), (1, 2), (5, 2)]

Edit：正如@jpp在注释中指出的那样，可以使用来自Counter的等价包装方法most_common来完成上述操作：

print(Counter(l).most_common(5))