我正在编写一个函数来查找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])
有一种简单的方法可以实现
我认为您的方法是使用另一个与“散列映射”一样大的数组。如果
k
很大,但唯一元素的数量不是很大,那么您将浪费大量空间。此外,要找到大多数,您必须遍历map_of
hashmap/数组来找到最大值另一方面,dictionary/set(不考虑散列,对于一般情况,底层数组结构可能更紧凑)似乎更合适一些。不用说,使用出现的元素作为键,它们的出现作为值,您可以在一次迭代中找到所需的内容。
所以,有点像:
正如所料,我们得到了我们想要的。
当然,计数器和其他很酷的模块可以让你用更精细的语法做你想做的事情。
Python有一个名为
Counter
的内置类,它将为您实现这一点。查看文档。
http://docs.python.org/2/library/collections.html#collections.Counter
相关问题 更多 >
编程相关推荐