Попытка найти элемент большинства в списке

Я пишу функцию, чтобы найти большинство в списке 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])

Ответы

Ответ 1

Я думаю, что ваш подход заключается в использовании другого массива размером k как вашего "хэш-карты". Если k огромен, но количество уникальных элементов не так велико, вы будете тратить много места. Кроме того, чтобы найти большинство, вам нужно будет пропустить ваш хэш-массив map_of, чтобы найти max.

С другой стороны, словарь/набор (где хеширование не является вашей проблемой, а основная структура массива, вероятно, будет более компактной для средних случаев) кажется немного более подходящей. Излишне говорить, что с появляющимися элементами как ключами и их вхождениями в качестве значений вы можете найти то, что хотите в одной итерации.

Итак, что-то вроде:

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)

Конечно, счетчики и другие классные модули позволят вам делать то, что вы хотите, в более тонком синтаксисе.

Ответ 2

У 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

Ответ 3

Существует простой способ реализовать это как

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