Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Trying to find majority element in a list

I'm writing a function to find a majority in a Python list.

Thinking that if I can write a hash function that can map every element to a single slot in the new array or to a unique identifier, perhaps for a dictionary, that should be the best and it should be undoable. I am not sure how to progress. My hash function is obviously useless, any tips on what I can/should do, or if this is even a reasonable approach?

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])
like image 639
bezzoon Avatar asked Nov 18 '13 00:11

bezzoon


People also ask

How do you determine majority?

Count the total number of votes cast. Divide the total by two. For an even-numbered total, add one to the result to find the threshold for the majority. For an odd total, round to the higher number for the majority.


2 Answers

There is an easy way to realize like this

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
like image 40
Xin Wang Avatar answered Oct 05 '22 06:10

Xin Wang


Python has a built-in class called Counter that will do this for you.

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

See the docs.

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

like image 132
FogleBird Avatar answered Oct 05 '22 06:10

FogleBird