- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
# -*- coding: utf-8 -*-
# На входе: не пустой b-массив
# На выходе: словарь из 1-ого элемента {самый часто встречающийся элемент:количество}
# 1. Сначала составляем словарь, потом ищем максимум и возвращаем
def Freq1(b):
assert len(b) > 0
d = {}
for x in b: # Пробегаем в цикле исходный массив
d[x] = d[x] + 1 if d.has_key(x) else 1 # Если ключ уже есть, прибавляем 1, если нет, записываем 1
v = max(d, key=d.get) # v ключ из словаря соответствующий максимальному значению
return {v:d[v]} # Возвращаем ответ
# 2. Ищем максимум прямо при составлении словаря
def Freq2(b):
d = {}
m, i = 0, 0 # Максимальная частота и индекс в словаре
for x in b: # Пробегаем в цикле исходный массив
d[x] = d[x] + 1 if d.has_key(x) else 1 # Если ключ уже есть, прибавляем 1, если нет, записываем 1
if d[x] > m:
m, i = d[x], x # Запоминаем максимум и его индекс
return {i:m}
# 3. Без использования словаря (сложность квадратичная - "тупой метод")
def Freq3(b):
m, i = 0, 0 # Максимальная частота и соответствующее ему значение
for x in b:
c = b.count(x) # Сколько раз встречается x в массиве b?
if c > m:
m, i = c, x
return {i:m}
# Проверка (примитивный unit-тест)
def Check(inData, expected):
assert Freq1(inData) == expected
assert Freq2(inData) == expected
assert Freq3(inData) == expected
Check(["banana", "banana", "apple", "banana", "banana", "apple", "onion"], {'banana': 4})
Check([2, 3, 9, 3, 6, 6], {3: 2})
Check([True, True, True, False, False, True], {True: 4})
Самый часто встречающийся элемент в массиве (3 способа).
Везде сплошной говнокод. Как ПРАВИЛЬНО найти самый часто встречающийся элемент в массиве?
Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
Follow us!
>>Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
сортировка требует времени
Например, строить сбалансированное бинарное дерево прямо при проходе массива, в узлах будет значение:количество?
У меня плохо с алгоритмами :)
зачем переусложнять? "За деревьями леса не видно" ©
вам надо задачу решить или на девушку произвести впечатление уровнем владения алгоритмами и технологиями? так вроде как не этим впечатляют испокон веку :)
во-во поэтому советую ебануть теоркатом: катаморфизмы, анаморфизмы, хиломорфизмы, параморфизмы наконец.
В прошлый раз в задаче поиска элемента и вставки в массив её препод сказал, что бинарный поиск ещё кое-как подходит :)
Я написал 5 вариантов: http://stden.livejournal.com/397391.html
1) массив совсем небольшой, и проще и быстрее всего прогнать итерацию insertion sort.
2) структура данных выбрана неверно, и нужно её менять целиком; например, использовать сортированный multiset.
dict((Counter(b).most_common()[0],))
Кортеж лишний
Если это лаба, то пофигу, лишь бы не квадратично.
Если бы это нужно сделать один раз в реальной жизни, я бы сделал так:
1) строим хэш таблицу со счётчиками за амортизированное O(N)
2) преобразуем её в массив пар за O(N)
3) строим max heap по частотам за O(log N)
4) вершина хипа - ответ за O(1)
Такой алгоритм работает за амортизированное O(N). Я почти уверен, что питоний Counter, упомянутый выше, примерно так и работает.
Если операция частая и/или может затрагивать подмассивы, гуглите Range Mode Query.
За O(N), конечно.