试图在列表中找到多数元素

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])

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

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

Answer 3

我认为你的方法是使用另一个k与你的"哈希映射" 一样大的数组.如果k是巨大的,但独特元素的数量不是很大,你会浪费很多空间.此外,要找到大多数,您必须遍历您的map_ofhashmap /数组才能找到最大值.

另一方面,字典/集合(其中散列不是您的关注点,并且基础数组结构对于普通情况可能更紧凑)似乎更合适.不用说,将出现的元素作为键并将它们作为值出现,您可以在一次迭代中找到所需的内容.

所以,像:

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)

当然,Counters和其他很酷的模块可以让你用更精细的语法做你想做的事.