Пару статей назад я уже рассматривала один из алгоритмов Бойера-Мура, с помощью которого можно было найти подстроку в строке.
Сегодня хочу поболтать об алгоритме большинства голосов, который позволяется найти преобладающий элемент последовательности.
Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.
Условие здесь: https://leetcode.com/problems/most-frequent-even-element/description/
Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно – жду здесь – t.me/crushiteasy 🙂
Возвращаемся к Муру!
Кратко: на вход мы получаем массив, состоящий из чисел. Нужно найти число, которое встречается наибольшее количество раз.
Не супер очевидно, но это число занимает больше половины элементов массива, т.е.
