在列表中尝试查找主要元素

Question

我正在编写一个函数，用于在Python列表中查找主要元素。

我在思考，如果我能编写一个哈希函数，将每个元素映射到新数组的单个插槽或唯一标识符，也许对于字典来说应该是最好的，而且它应该是可逆的。我不确定如何继续下去。我的哈希函数显然是无用的，有什么提示可以提供给我该怎么做或者这是否是一个合理的方法？

def find_majority(k):
    def hash_it(q):
        return q

    map_of = [0]*len(k)

    for i in k:
        mapped_to = hash_it(i) #hash function
        map_of[mapped_to]+=1


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

- bezzoon

---

在Python中，你最好使用字典而不是自己编写哈希函数，因为该语言极力阻止你这样做。 - Patrick Collins

你想要找到最常见的元素还是主要元素（出现次数超过N/2）？ - jfs

Answer 1

Python内置了一个名为Counter的类，可以帮助你实现这个功能。

>>> from collections import Counter
>>> c = Counter([1,2,3,4,3,3,2,4,5,6,1,2,3,4,5,1,2,3,4,6,5])
>>> c.most_common()
[(3, 5), (2, 4), (4, 4), (1, 3), (5, 3), (6, 2)]
>>> value, count = c.most_common()[0]
>>> print value
3

请查看文档。

http://docs.python.org/2/library/collections.html#collections.Counter

- FogleBird

---

使用 c.most_common(1)[0] -- max() 和 sort() 的比较。 - jfs

除非你自己检查并处理平局，否则仍需要进行检查。 - berniethejet

Answer 2

有一种简单的方法可以实现这样的效果

l = [1,2,3,4,3,3,2,4,5,6,1,2,3,4,5,1,2,3,4,6,5]
print(max(set(l), key = l.count)) # 3

- Xin Wang

---

这真的很简洁！请注意，这需要O（len(set(l)) * len(l)）时间，因为它调用了l.count（一个O（len(l)）操作）len(set(l))次，而如果我们事先创建一个计数器，我们可以在O（len(l)）时间内完成此操作。 - mic

Answer 3

我认为您的方法是使用另一个与 k 同样大的数组作为您的“哈希表”。如果 k 很大但唯一元素的数量并不是很大，那么您将浪费很多空间。此外，要找到大多数，您必须遍历您的 map_of 哈希表/数组以查找最大值。

另一方面，字典/集合（其中哈希不是您的关注点，并且基础数组结构可能更紧凑）似乎更加适合。不用说，使用出现的元素作为键，它们的出现次数作为值，你可以在一次迭代中找到你想要的内容。

因此，类似于：

def find_majority(k):
    myMap = {}
    maximum = ( '', 0 ) # (occurring element, occurrences)
    for n in k:
        if n in myMap: myMap[n] += 1
        else: myMap[n] = 1

        # Keep track of maximum on the go
        if myMap[n] > maximum[1]: maximum = (n,myMap[n])

    return maximum

正如预期的那样，我们得到了想要的结果。

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

当然，计数器和其他酷炫的模块将让您在更精细的语法中实现所需的功能。

- slider

---

太棒了！我实际上用字典的方式解决了它，非常相似的方法 = ) ! - bezzoon