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

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

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

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

Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем [math]N / K[/math] раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает за [math]O(N \cdot K)[/math]

Псевдокод

Доказательство

Источники

• Habrahabr - Поиск часто встречающихся элементов в массиве
• Algolist - Решение задачи 15