Нахождение преобладающего элемента последовательности (алгоритм большинства голосов Бойера-Мура)

Пару статей назад я уже рассматривала один из алгоритмов Бойера-Мура, с помощью которого можно было найти подстроку в строке.

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

Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.

Условие здесь: https://leetcode.com/problems/most-frequent-even-element/description/

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Возвращаемся к Муру!

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

Не супер очевидно, но это число занимает больше половины элементов массива, т.е.


Читать: https://habr.com/ru/articles/833932/?utm_campaign=833932

@a_cup_of_java | Другие наши каналы