Мажорирующий элемент

Материал из Викиконспекты
Версия от 12:04, 24 мая 2013; 188.227.78.59 (обсуждение) (Создание скелета)
Перейти к: навигация, поиск

Формулировка задачи

Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз.

Решение за O(n)

Обобщение на случай поиска элемента, встречающегося N/K раз

"Хитрое" решение

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Мажорирующий_элемент&oldid=30756»