Python: 获取列表中出现最频繁的元素

Question

给定一个元组列表，我想要获取出现最频繁的元组，但如果有“并列获胜者”，则应随机选择其中一个。

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

以上列表应在随机情况下返回 (1,2) 或 (3,4)。

- Juddling

Answer 1

使用collections.Counter：

>>> collections.Counter([ (1,2), (3,4), (5,6), (1,2), (3,4) ]).most_common()[0]
((1, 2), 2)

这是 O(n log(n)) 复杂度。

- simonzack

---

实际上，如果您需要最常见的项目，则可以在O（n）中完成。您只需计算频率，获取最大值，然后获取所有具有最高频率的项目。至少有4个人不知道这一点 :) - Roman Pekar

无法在O(n)时间内完成此操作，因为计算所有频率需要使用某种哈希表。 - simonzack

据我所知，计数器是作为字典实现的，并且字典元素的设置平均为O(1)。在你的答案中，most_common()方法将对所有元素进行排序，因此它将是最重要的部分 - O(n log(n))。 - Roman Pekar

Answer 2

你可以首先使用Counter来找到最常重复的元组，然后找到所需的元组，最后随机化并获取第一个值。

from collections import Counter
import random

tups = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]
lst = Counter(tups).most_common()
highest_count = max([i[1] for i in lst])
values = [i[0] for i in lst if i[1] == highest_count]
random.shuffle(values)
print values[0]

- Sudip Kafle

---

@Juddling 其实，你不需要使用most_common() - 可以看看我的回答。 - Roman Pekar

@RomanPekar 我明白了，为什么我要避免使用most_common()函数呢？ - Juddling

如果我没记错的话，most_common() 函数会对整个列表进行排序，你只需要获取最大频率即可。 - Roman Pekar

Answer 3

您可以首先对列表进行排序，以按频率排序的元组。之后进行线性扫描即可从列表中获取最常见的元组。总时间为O(nlogn)。

>>> tups = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]
>>> 
>>> sorted(tups)
[(1, 2), (1, 2), (3, 4), (3, 4), (5, 6)]

- Srikar Appalaraju

Answer 4

这个可以在O(n)的时间内完成任务：

>>> from random import shuffle
>>> from collections import Counter
>>>
>>> tups = [(1,2), (3,4), (5,6), (1,2), (3,4)]
>>> c = Counter(tups)                            # count frequencies
>>> m = max(v for _, v in c.iteritems())         # get max frq
>>> r = [k for k, v in c.iteritems() if v == m]  # all items with highest frq
>>> shuffle(r)                                   # if you really need random - shuffle
>>> print r[0]
(3, 4)

- Roman Pekar

---

这不是 O(n)，考虑所有元素都是唯一的情况。 - simonzack

字典中元素的设置时间复杂度为O(1)平均。 - Roman Pekar

Answer 5

这是另一个没有导入的示例：

listAlphaLtrs = ['b','a','a','b','a','c','a','a','b','c','c','b','a','a','a']
dictFoundLtrs = {i:listAlphaLtrs.count(i) for i in listAlphaLtrs}
maxcnt = 0
theltr = 0
for ltr in dictFoundLtrs:
    ltrfound = ltr
    foundcnt = dictFoundLtrs[ltr]
    if foundcnt > maxcnt:
        maxcnt = foundcnt
        theltr = ltrfound
print('most: ' + theltr)

来源：

https://dev59.com/-WAg5IYBdhLWcg3wvNCF#23240989

- cssyphus

Answer 6

使用 collections.Counter 进行计数，然后随机选择最常见的元素：

import collections
import random

lis = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]  # Test data
cmn = collections.Counter(lis).most_common()  # Numbering based on occurrence
most = [e for e in cmn if (e[1] == cmn[0][1])]  # List of those most common
print(random.choice(most)[0])  # Print one of the most common at random

- Morten Zilmer