Наиболее часто встречающийся элемент
Имеется массив, нужно найти в нем максимальный элемент среди наиболее часто встречающихся. Я делал вот так. Ввод данных с клавиатуры:
n = int(input()) new = list(map(int, input().split())) Сопоставление каждому элементу из массива его частоты (количество вхождений):
mydict = <> for elem in new: mydict[elem] = 0 for elem in new: mydict[elem] = mydict[elem] + 1 А как быть дальше? Можно ли за линию вытащить наиболее встречающийся элемент с наибольшем значением?
Отслеживать
задан 25 фев 2022 в 18:33
Water Lily Water Lily
23 1 1 серебряный знак 3 3 бронзовых знака
Нужно найти максмальное значение среди дублей в списке, так?
25 фев 2022 в 18:47
@ZheniaKviatkivskyi: да, все так.
25 фев 2022 в 23:33
4 ответа 4
Сортировка: Сброс на вариант по умолчанию
Дополнение к вашему коду. Вы бежите по парам элемент/счётчик и выбираете из них самую большую, сперва по счётчику, затем по значению (для этого lambda ):
item, count = max(mydict.items(), key=lambda p: p[::-1]) Ваш код можно доработать используя collections.Counter:
import collections input() # skip line c = collections.Counter(map(int, input().split())) item, count = max(c.items(), key=lambda p: p[::-1]) print(item, count) Говнокод: по колено в коде.
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
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.
Найти наиболее часто встречаемый элемент столбца матрицы, наименее часто встречаемый элемент другого столбца
Есть матрица, в ней 2 столбца и n строк, т. е. произвольное значение, элементы в строках рандомные. Нужно найти наиболее часто встречаемый элемент столбца матрицы, наименее часто встречаемый элемент другого столбца. Вывести необходимо
самый популярный элемент первого столбца, самый непопулярный элемент второго столбца, если какие-то элементы вместе являются самыми популярными, или самыми непопулярными, вывести 0.
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Наиболее часто встречаемый элемент файла записей
Дан типизированный файл записей каждая запись — сведения о каком-нибудь спортсмене(возраст.
Функция возвращающая наиболее часто встречаемый символ
Прошу помощи , по скольку сам новичок , не очень понимаю как сделать . Написать функцию, которая.
Написать функцию которая находит в строке наиболее часто встречаемый символ
Помогите пожалуйста написать программу. Написать функцию, которая принимает строку и.
Во входном файле записана строка символов. Вывести наиболее часто встречаемый символ
Здравствуйте! Возник такой вопрос. Во входном файле записана строка символов. Вывести наиболее.
1391 / 675 / 300
Регистрация: 05.09.2021
Сообщений: 1,155
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
from random import randint n = 30 a = [[randint(1, 10) for _ in range(n)] for _ in range(2)] print(*a, sep='\n') b = [{i: a[j].count(i) for i in a[j]} for j in range(2)] max_value = max(b[0].values()) min_value = min(b[1].values()) res = ([k for k, v in b[0].items() if v == max_value], [k for k, v in b[1].items() if v == min_value]) if res[0] != res[1]: print(res[0][0], res[1][0]) else: print(0)
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Найти самый часто встречаемый цвет в изображении (PNG) и заменить его на введенный пользователем
Дано изображение в формате png. Функция должна найти самый часто встречаемый цвет, и заменить его.
Самый часто встречаемый символ в массиве
А как можно найти наиболее часто встречающийся символ в массиве из х элементов
В списке найти наиболее часто встречающийся элемент
С кодом проблемы не могу заменить массивы на списки #include <iostream> using namespace std;.
Найти наиболее часто встречающийся элемент массива
Дан массив из 40 элементов. Каждый элемент может принимать целочисленные значения от 0 до 200.
Найти в vector-е наиболее часто встречающийся элемент
Допустим, что у нас есть вектор: как найти наиболее часто встречающийся элемент в этом векторе?
В массиве целых чисел найти наиболее часто встречающееся число
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число.Если таких чисел несколько , то определить наименьшее из них.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Найти наиболее часто встречающееся число
Используя модуль Tkinter, создайте графический интерфейс для программы, решающий следующую задачу.
В массиве целых чисел найти наиболее часто встречающееся число
Задание. Написать алгоритм на языке С++. В массиве целых чисел из n элементов найти наиболее часто.
В массиве целых чисел размерности n найти наиболее часто встречающееся число
Здравствуйте, прошу помочь в решении задачи:sorry: В массиве целых чисел размерности n найти.
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число
Если таких чисел несколько, то определить наименьшее из них и вывести его.
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,102
Записей в блоге: 6
Один из вариантов:
1 2 3 4
import numpy as np # пусть x - наш массив. bc = np.bincount(x) np.arange(len(bc))[bc == bc.max()].min()
Добавлено через 8 минут
Есть более простой вариант. Вместо последней строки —
bc.argmax()
Но тут мы надеемся на подходящее поведение функции в неопределённой, в общем, ситуации, а именно — что argmax из всех максимальных элементов берёт именно первый.
Регистрация: 06.05.2015
Сообщений: 7
А нельзя написать код через range?
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,102
Записей в блоге: 6
Регистрация: 06.05.2015
Сообщений: 7
Нельзя как то проще написать код?
4615 / 2036 / 359
Регистрация: 17.03.2012
Сообщений: 10,102
Записей в блоге: 6
Сообщение было отмечено Tatiana933 как решение
Решение
Да куда уж проще-то, две строки всего.
Но можно и так, но это неспортивно:
from collections import Counter Counter(x).most_common()[0]
Там увидите, что есть что.
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
В массиве целых чисел с количеством элементов п найти наиболее часто встречающееся число
В массиве целых чисел с количеством элементов п найти наиболее часто встречающееся число. Если.
В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число
В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число.
В массиве целых чисел найти наиболее часто встречающееся число. Если таких чисел несколько, то определить наим
Вообщем не понял сути самого задания. Разъясните иль если сможете помогите сделать.
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если.
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве
Основная проблема в том, что нельзя использовать сторонние библиотеки, даже функцию sort, в общем.
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве
Задан массив из k чисел. Найти число, наиболее часто встречающееся в этом массиве