Вывести наиболее часто встречающийся элемент массива python

Python — найти элемент с максимальным количеством появлений в списке

В Python у меня есть список:

Я хочу идентифицировать предмет, который встречался наибольшее количество раз. Я могу решить это, но мне нужен самый быстрый способ сделать это. Я знаю, что есть хороший ответ Pythonic на это.

13 ответов

Вот defaultdict решение, которое будет работать с Python версий 2.5 и выше:

Обратите внимание, если L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67] тогда есть шесть четверок и шесть семерок. Тем не менее, результатом будет (4, 6) , то есть шесть четверок.

Может что-то вроде этого:

testList = [1, 2, 3, 4, 2, 2, 1, 4, 4] print(max(set(testList), key = testList.count))

Простой способ без каких-либо библиотек или наборов

Мой (простой) код (три месяца изучения Python):

Ниже приводится решение, которое я придумал, если в строке несколько символов, все из которых имеют самую высокую частоту.

Вход: «привет люди»

Самая высокая частота встречаемости: 3

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

Вы можете сравнить это с кодом, предоставленным Недом Дейли, который даст вам эти результаты для самого маленького теста:

Но будьте осторожны, это неэффективно, и поэтому действительно работает медленно для больших списков!

Я удивлен, что никто не упомянул самое простое решение, max() с ключом list.count :

Это работает в Python 3 или 2, но обратите внимание, что он возвращает только самый частый элемент, а не частоту. Кроме того, в случае рисования (то есть совместного наиболее часто используемого элемента) возвращается только один элемент.

Хотя временная сложность использования max() хуже, чем использование Counter.most_common(1) в качестве комментариев PM 2Ring этот подход выигрывает от быстрой реализации C , и я считаю, что этот подход наиболее быстр для коротких списков, но медленнее для более крупных (времен Python 3.6, показанных в IPython 5.3):

Если вы используете Python 3.4 или выше, вы можете использовать <>

Обратите внимание, что при этом будет выбрано statistics.StatisticsError , если список пуст или если не существует только одного наиболее распространенного значения.

Я получил лучшие результаты с groupby из модуля itertools с этой функцией, используя Python 3.5.2:

Тест с timeit из модуля timeit .

Я использовал этот скрипт для своего теста с number= 20000 :

Простой и лучший код:

Результат: 4 встречается 6 раз

В вашем вопросе вы попросили самый быстрый способ сделать это. Как уже неоднократно демонстрировалось, особенно с Python, интуиция не является надежным руководством: вам нужно измерять.

Вот простой тест нескольких разных реализаций:

Результаты на моей машине:

Похоже, что решение Counter не самое быстрое. И, по крайней мере, в этом случае groupby быстрее. defaultdict это хорошо, но вы платите немного за его удобство; немного быстрее использовать обычный dict с get .

Что произойдет, если список намного больше? Добавляем L *= 10000 к тесту выше и уменьшаем количество повторений до 200:

Теперь defaultdict явный победитель. Так что, возможно, стоимость метода get и потери добавленного на месте складывается (проверка сгенерированного кода оставлена в качестве упражнения).

Но с измененными тестовыми данными число уникальных значений элементов не изменилось так, предположительно, dict и defaultdict имеют преимущество в этом отношении по сравнению с другими реализациями. Так что же произойдет, если мы воспользуемся большим списком, но существенно увеличим количество уникальных предметов? Замена инициализации L на:

Так что теперь Counter явно быстрее, чем решения groupby , но все же медленнее, чем iteritems версии dict и defaultdict .

Смысл этих примеров не в том, чтобы найти оптимальное решение. Дело в том, что часто не существует одного оптимального общего решения. Плюс есть и другие критерии эффективности. Требования к памяти будут существенно различаться в зависимости от решения, и по мере увеличения размера ввода требования к памяти могут стать определяющим фактором при выборе алгоритма.

Источник

Найти число встречающееся в списке наибольшее количество раз

Напишите программу, которая находит в данном списке A число, которое встречается в списке наибольшее число раз.
ВХОДНЫЕ ДАННЫЕ

Программа получает на вход несколько чисел (не более 1000), записанных в одной строке через пробел. Все числа по модулю не превосходят 109.
ВЫХОДНЫЕ ДАННЫЕ

Программа должна вывести единственное число — число, которое встречается чаще всех из данных. Если таких чисел несколько, то нужно вывести наибольшее из них.

ВВОД
3 5 1 2 5
ВЫВОД
5

ВВОД
3 5 4 4 3
ВЫВОД
4

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Как найти число, встречающееся чаще всего?
Всем привет! Нужна небольшая помощь с задачкой. Вот собственно и она.

В массиве целых чисел найти наиболее часто встречающееся число
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число.Если таких.

Сколько раз в списке встречается наибольшее значение?
Народ,есть функция print, которая выводит максимальное значения списка. А как сделать так, чтобы.

Одномерные массивы. Найти число, встречающееся наибольшее количество раз
Задан массив целых чисел от -100 до 100. Найти число, встречающееся наибольшее количество раз

Источник

Как из массива вытащить 3 наиболее часто повторяющихся элемента?

Господа помогите: Как мне из массива вытащить 3 наиболее часто повторяющихся элемента и сколько раз он повторился? Не соображу как сделать именно 3 наибольших. Ну или 5 — не важно — главное не все повторяющиеся (это можно через Counter), а конкретное количество самых частых.

Предположим есть массив слов:

В результате мне нужно получить что то вроде:

2 ответа 2

или в виде словаря:

Если есть желание использовать только core -методы, то можно сделать так:

Тогда res будет:

Ну и соответственно, dict(res) :

Всё ещё ищете ответ? Посмотрите другие вопросы с метками python python-3.x list словари или задайте свой вопрос.

Похожие

Подписаться на ленту

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2021 Stack Exchange Inc; материалы пользователей предоставляются на условиях лицензии cc by-sa. rev 2021.11.2.40635

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Источник

Как найти число, чаще всего встречающееся в массиве?

Здравствуйте. Пытаюсь решить задачу, но не знаю, с помощью чего. Нашла несколько методов, но ни один не работает.
Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве.

Находила такой пример (вне форума, а на форуме тоже не работает то, что находила):

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Как найти число, встречающееся чаще всего?
Всем привет! Нужна небольшая помощь с задачкой. Вот собственно и она.

Найти и напечатать число, чаще других встречающееся в массиве
Сформировать массив 100 целых случайных чисел в диапазоне от 0 до 9. Напечатать его. Найти и.

Найти и напечатать число, чаще других, встречающееся в массиве
Сформировать массив 100 целых случайных чисел в диапазоне от 0 до 9. Напечатать его. Найти и.

Найти и напечатать число, чаще других, встречающееся в массиве
Сформировать массив 100 целых случайных чисел в диапазоне от 0 до 9. Напечатать его. Найти и.

ошибку при компиляции выдает

Добавлено через 51 секунду
Забыла, еще требование к заданию: «Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a.»

Добавлено через 18 минут
В общем, на исходный код

выводит следующее:
Вывод постпроцессора
stdout:
0

Т.е. какую-то ерунду.

Добавлено через 1 минуту

на это выводит следующее:
stdout:

stderr:
Traceback (most recent call last):
File «/temp/compiling/compilingScript», line 17, in
py_compile.compile(dst, doraise=True)
File «/usr/lib/python2.7/py_compile.py», line 117, in compile
raise py_exc
py_compile.PyCompileError: SyntaxError: (‘invalid syntax’, (‘/temp/compiling/3635c1aa-696e-40b2-bb32-ca2bceef130e’, 7, 2, ‘>>> arr = [int(random() * 20) for _ in range(15)]\n’))

Вывод постпроцессора
stdout:
0

Благодарю, Марина!
Только пишет ошибку представления теперь.

Там полное задание такое:
Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве.

Формат ввода
В первой строке входных данных записано число n (1 ≤ n ≤ 300 000). Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 1 000 000 000).

Формат вывода
Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a.

Добавлено через 1 минуту

Решение

Массив: Найти и напечатать число, чаще других, встречающееся в массиве.
Помогите! Заранее спасибо! Задача: Сформировать массив 100 целых случайных чисел в диапазоне от 0.

С помощью указателей найти и напечатать число, чаще других встречающееся в массиве
1 задача с++ В динамической памяти ЭВМ Сформировать массив 100 целых случайных чисел в диапазоне.

Найти в строке слово, встречающееся чаще всего
Задача найти в строке слово ,встречающееся чаще всего. Ввожу строку ,делю её на слова и их в массив.

Найти слово, встречающееся чаще всего в данном текстовом файле
Парни нужна помощь, задали задачку на сдачу, а я не шарю как сделать: Есть файл с текстом. Найти.

Найти число в двумерном массиве, которое чаще всего повторяется
Найти число в двумерном массиве, которое чаще всего повторяется.

Слово, встречающееся чаще всего
Runtime error( Дан текст. Выведите слово, которое в этом тексте встречается чаще всего. Если таких.

Источник

Поиск часто встречающихся элементов в массиве

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary , за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.

Реализация алгоритма Бойера-Мура занимает всего несколько строк:

В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.

Усложним задачу. Теперь в массиве длиной N надо найти элементы, которые повторяются больше N/3 раз — если есть два, то оба, если есть один, то один.

Например, нашему устройству с маленькой памятью нужно принять двоичный сигнал с неизвестными уровнями нуля и единицы, но известно, что примерно половину времени передаётся ноль, примерно половину времени — единица, а любые отличные от них уровни сигнала — это помехи и дребезг от переключения.

Идею прошлого алгоритма несложно обобщить и для троек: пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.

Код мало отличается от предыдущего: по-прежнему один проход по массиву и O(1) дополнительной памяти.

Этот алгоритм опубликован в 1982 американскими учёными Джаядевом Мисрой и Дэвидом Грисом (Jayadev Misra & David Gries), и в их работе используется более скучная метафора — мешок с N числами, из которого они извлекают по 3 разных числа за каждую операцию. Кроме того, их псевдокод не похож ни на один понятный современному программисту язык. Мне больше понравилось объяснение их алгоритма в позапрошлогоднем конспекте лекций американского профессора Амита Чакрабарти.

В наиболее общей форме, когда в массиве длиной N надо найти элементы, которые повторяются больше N/k раз — придётся-таки воспользоваться словарём. Хранить в словаре мы будем только те элементы, с которыми люди стоят — т.е. не больше k-1 записей.

В этой наиболее общей форме алгоритма — по-прежнему один проход по массиву и O(k) дополнительной памяти. Если мы пользуемся для реализации словаря хэш-таблицей, а все записи в словаре свяжем в список — тогда общая сложность алгоритма останется линейной: строчка (*) с удалением записи из словаря выполняется самое большее N раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

Таким образом наше устройство с маленькой памятью смогло бы общаться с одним пушистым зверьком, недавно препарированным хабраумельцами. Сигналы этого зверька имеют пять логических уровней: полагаем k=6, и получаем все пять уровней прямо на ходу, даже без сохранения сигнала в память. Нужно только обеспечить протоколом, чтобы все пять уровней встречались в сигнале одинаково часто.

Для алгоритма Мисры-Гриса упоминаются и другие применения. Например, можно следить в реальном времени за трафиком в сети, и если некий один хост потребляет непропорционально большую часть трафика — начинать расследование. Так же можно следить за кликами по баннерам, за финансовыми транзакциями, за потоком инструкций в моделируемом процессоре… В общем, всюду, где большое число повторений — подозрительная аномалия.

За оживление текста иллюстрациями надо благодарить Nitatunarabe

Источник