UniLecs #Task. Majority element 2
Задача: дан числовой массив размера N. Необходимо найти все элементы (если такие существуют), ктр встречаются в массиве более чем [N / 3] раз (округление в меньшую сторону).
Условие: решить за линейное время O(N), а также O(1) по памяти (т.е. не использовать доп.структур для хранения элементов массива).
Входные данные: arr — числовой массив размера N, где N от 1 до 10000. Элементы массива — любые действительные числа.
Вывод: вывести мажоритарные элементы массива (если такой существует), иначе сообщение о его отсутствии.
Примеры:
- nums = [1, 2, 1]
Output: [1] - nums = [1,2]
Output: [1, 2] - nums = [1, 2, 3, 4]
Output: []
Разбор
Первая идея, ктр возникает при решении задачи на поиск мажоритарного элемента, это решение через словарик, где ключ это элемент массива, а значение — кол-во его вхождений. Все просто и понятно. Но это решение использует O(N) доп.памяти. Можно ли обойтись O(1) доп.памяти при той же скорости O(N)?
Ответ да, существует известный алгоритм Бойера-Мура, ктр можно переформулировать следующим образом:
“На вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.”
В конце мы получим «наиболее вероятного кандидата» на присутствие в N/2 экземплярах:
- если такой элемент в массиве действительно существует, то он будет найден;
- если же такого элемента нет, то возможно, мы просто нашли элемент, которому не хватило пары.
Для более строгой реализации majority требуется пройти по массиву 2й раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.
Случай для [N/3] не сильно усложняет задачу и ее можно переформулировать так:
“Пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.”
Детали реализации смотрите ниже.
Реализация
https://gist.github.com/unilecs/61a79304daf1712fcbd9da2d9592762a
