Ctrl K

Победитель с большинством голосов

Лёгкая
Прошло голосование: каждый элемент массива votes — номер кандидата, за которого отдан бюллетень. Известно, что один кандидат получил **строго больше половины** всех голосов. Верните номер этого кандидата. Подсчёт через словарь очевиден. Сможете обойтись линейным временем и O(1) дополнительной памяти?
Пример 1
votes=[7, 4, 7, 7, 2] → 7

Кандидат 7 набрал 3 голоса из 5 — больше половины.

Пример 2
votes=[-5] → -5

Единственный бюллетень — и он же большинство.

Пример 3
votes=[1, 9, 9, 1, 9, 1, 9] → 9

У 9 четыре голоса из семи, у 1 — только три.

Ограничения
  • 1 ≤ len(votes) ≤ 5·10⁴
  • -10⁹ ≤ votes[i] ≤ 10⁹
  • Кандидат, набравший больше len(votes) / 2 голосов, всегда есть
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамые частые значения СредняяСоседние значения ЛёгкаяЕсть в каждом списке ЛёгкаяБольше трети голосов СредняяЗадания с перерывом на остывание Средняя
загружаем Python…
Вход
votes=[7, 4, 7, 7, 2]
Ожидается
7

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 41 тест на сервере, включая скрытые.