Мажорирующий элемент — различия между версиями
Никита (обсуждение | вклад) (→Доказательство) |
Никита (обсуждение | вклад) (→Формулировка задачи) |
||
Строка 1: | Строка 1: | ||
== Формулировка задачи == | == Формулировка задачи == | ||
− | Требуется в массиве длиной ''N'' найти элемент, встречающийся более ''N/2'' раз. | + | Требуется в массиве длиной ''N'' найти элемент, встречающийся более ''N/2'' раз. Гарантируется, что такой элемент существует. |
== Решение за O(n) == | == Решение за O(n) == |
Версия 13:16, 24 мая 2013
Содержание
Формулировка задачи
Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз. Гарантируется, что такой элемент существует.
Решение за O(n)
Обобщение на случай поиска элемента, встречающегося N/K раз
"Хитрое" решение
Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем
раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает заПсевдокод
findMajorityElement(a, N, K) while true candidate = a[random(N)] count = 0 for i = 0 to N - 1 if a[i] == candidate count++ if count > N / K return candidate
Доказательство
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за
. Вероятность, что мы выбрали элемент "удачно" составляет . Тогда, в среднем, мы будем делать шагов. Итоговая сложность .