Поиск максимального значения в списке на Python
В этой статье мы научимся находить максимальное значение в списке на Python. Для всестороннего понимания вопроса мы рассмотрим использование некоторых встроенных функций, простые подходы, а также небольшие реализации известных алгоритмов.
Сначала давайте вкратце рассмотрим, что такое список в Python и как найти в нем максимальное значение или просто наибольшее число.
Список в Python
В Python есть встроенный тип данных под названием список (list). По своей сути он сильно напоминает массив. Но в отличие от последнего данные внутри списка могут быть любого типа (необязательно одного): он может содержать целые числа, строки или значения с плавающей точкой, или даже другие списки.
Хранимые в списке данные определяются как разделенные запятыми значения, заключенные в квадратные скобки. Списки можно определять, используя любое имя переменной, а затем присваивая ей различные значения в квадратных скобках. Он является упорядоченным, изменяемым и допускает дублирование значений. Например:
list1 = ["Виктор", "Артем", "Роман"] list2 = [16, 78, 32, 67] list3 = ["яблоко", "манго", 16, "вишня", 3.4]Далее мы рассмотрим возможные варианты кода на Python, реализующего поиск наибольшего элемента в списке, состоящем из сравниваемых элементов. В наших примерах будут использоваться следующие методы/функции:
- Встроенная функция max()
- Метод грубой силы (перебора)
- Функция reduce()
- Алгоритм Heap Queue (очередь с приоритетом)
- Функция sort()
- Функция sorted()
- Метод хвостовой рекурсии
№1 Нахождение максимального значения с помощью функции max()
Это самый простой и понятный подход к поиску наибольшего элемента. Функция Python max() возвращает самый большой элемент итерабельного объекта. Ее также можно использовать для поиска максимального значения между двумя или более параметрами.
В приведенном ниже примере список передается функции max в качестве аргумента.
Как найти наиболее часто встречающийся элемент в массиве python
О Хекслете
01 ноября 2021
- python строки
- python массивы
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
01 ноября 2021
- python массивы
- python строки
- 8 800 100 22 47 бесплатно по РФ
- +7 495 085 28 38 бесплатно по Москве
Направления
- Курсы «Backend-разработка»
- Курсы «Frontend-разработка»
- Курсы «Создание сайтов»
- Курсы «Тестирование»
- Курсы «Аналитика данных»
- Интенсивные курсы
- Курсы DevOps
- Курсы «Веб-разработка»
- Курсы «Математика для программистов»
- Все курсы
О Хекслете
- О нас
- Карьера в Хекслете
- Хекслет Колледж
ООО «Хекслет Рус» 432071, г. Ульяновск, пр-т Нариманова, дом 1Г, оф. 23 ОГРН 1217300010476
- Справка
- Вопросы и ответы
- Сообщество
- Дополнительно
- Условия использования
- Соглашение об обработке ПД
- Оферта
- Акции
Подсчет наиболее часто встречающихся элементов в итерируемом объекте
Инструмент Counter из модуля collections очень полезен. В частности, с его помощью можно узнать, какие элементы списка или, скажем, какие символы в строке встречаются чаще всего, и сколько раз.
>>> import collections >>> c = collections.Counter('helloworld') >>> c Counter() >>> c.most_common(3) [('l', 3), ('o', 2), ('e', 1)]
Три наиболее часто встречающихся буквы в строке helloworld — l (3 раза), o (2 раза) и e (1 раз).
Говнокод: по колено в коде.
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
Python / Говнокод #4317
−94
# -*- 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 # Возвращаем ответ # 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 # 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 # Проверка (примитивный 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"], ) Check([2, 3, 9, 3, 6, 6], ) Check([True, True, True, False, False, True], )Самый часто встречающийся элемент в массиве (3 способа).
Везде сплошной говнокод. Как ПРАВИЛЬНО найти самый часто встречающийся элемент в массиве?
Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
Запостил: denis, 09 Октября 2010
Комментарии (15) RSS
Мистер Хэнки 09.10.2010 12:44 # +1
1й вариант со словарём самый оптимальный, если у вас нет ограничений на использование памяти и т.д.
>>Наверное, можно ещё отсортировать массив и пробежать по нему храня текущий элемент и количество и обновляя соответствующие переменные?
сортировка требует времени
denis 09.10.2010 14:47 # −2
Просто мне кажется, что я считаю зачем-то количество всех элементов. Может можно как-то отсекать редко встречающиеся элементы.
Например, строить сбалансированное бинарное дерево прямо при проходе массива, в узлах будет значение:количество?
У меня плохо с алгоритмами 🙂
Мистер Хэнки 09.10.2010 16:53 # +1
>Например, строить сбалансированное бинарное дерево прямо при проходе массива, в узлах будет значение:количество?
зачем переусложнять? "За деревьями леса не видно" ©
вам надо задачу решить или на девушку произвести впечатление уровнем владения алгоритмами и технологиями? так вроде как не этим впечатляют испокон веку 🙂
xXx_totalwar 09.10.2010 17:00 # 0
>вам надо задачу решить или на девушку произвести впечатление уровнем владения алгоритмами и технологиями? так вроде как не этим впечатляют испокон веку 🙂
во-во поэтому советую ебануть теоркатом: катаморфизмы, анаморфизмы, хиломорфизмы, параморфизмы наконец.
denis 09.10.2010 17:02 # 0
Мне нужно написать самое простое решение задачи, которое удовлетворило бы её препода.
В прошлый раз в задаче поиска элемента и вставки в массив её препод сказал, что бинарный поиск ещё кое-как подходит 🙂
Я написал 5 вариантов: http://stden.livejournal.com/397391.html
roman-kashitsyn 30.06.2015 12:05 # 0
Вставку в отсортированный сырой массив без разницы как делать, ибо эта операция обречена на O(N) независимо от алгоритма. Если вообще такое понадобилось делать - значит
1) массив совсем небольшой, и проще и быстрее всего прогнать итерацию insertion sort.
2) структура данных выбрана неверно, и нужно её менять целиком; например, использовать сортированный multiset.
denis 09.10.2010 14:47 # 0
Также, может есть встроенная функция чтобы это сделать?
telnet 09.10.2010 12:45 # 0
Сессия ж нескоро, неужто уже с курсачами зажимают?
denis 09.10.2010 14:49 # 0
Да, это я помогаю знакомой девушке. Просто я ей пишу как бы я сделал (я сам только начинаю программировать на Python) и мне постоянно кажется, что мои решения не python'овские. В Java я себя чувствую намного уверенней. Я привык копаться в больших Java-проектах и уже примерно знаю что там и как делается.
telnet 09.10.2010 16:25 # +2
Тематика сайта - смехотворный код, а не взаимная помощь и не pastebin. Чтобы это понять, не нужно знание Python'а, нужно знание русского, чтобы прочитать, что написано в шапке страницы, и логика, чтобы, просмотрев хотя бы несколько страниц, убедиться в справедливости написанного. Я не модератор, чтобы указывать, да. Тут вообще модераторов нет. Но Вы не первый, кто приходит сюда за помощью, и смотреть на оффтопик лично я уже подустал. Без обид. Найдёте кусок идиотского кода на той же Jav'е - постите сюда, посмеёмся вместе, опять же.
denis 09.10.2010 14:51 # 0
Например, я почти не использую генераторы и лямбда-выражения, потому что ещё просто не чувствую когда их правильно применять (т.е. есть некоторые очевидные случаи - генерация последовательности с заданными свойствами, это понятно), а вот общее правило??
intestinalbrain 30.06.2015 11:50 # +1
from collections import Counter
dict((Counter(b).most_common()[0],))
3_14dar 30.06.2015 12:22 # 0
roman-kashitsyn 30.06.2015 12:21 # 0
> Как ПРАВИЛЬНО найти самый часто встречающийся элемент в массиве?
Если это лаба, то пофигу, лишь бы не квадратично.
Если бы это нужно сделать один раз в реальной жизни, я бы сделал так:
1) строим хэш таблицу со счётчиками за амортизированное O(N)
2) преобразуем её в массив пар за O(N)
3) строим max heap по частотам за O(log N)
4) вершина хипа - ответ за O(1)
Такой алгоритм работает за амортизированное O(N). Я почти уверен, что питоний Counter, упомянутый выше, примерно так и работает.
Если операция частая и/или может затрагивать подмассивы, гуглите Range Mode Query.