Мажорирующий элемент — различия между версиями
(Создание скелета) |
(→"Хитрое" решение) |
||
| Строка 8: | Строка 8: | ||
== "Хитрое" решение == | == "Хитрое" решение == | ||
| + | |||
| + | Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем <tex>N / K</tex> раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает за <tex>O(N \cdot K)</tex> | ||
| + | |||
| + | === Псевдокод === | ||
| + | |||
| + | |||
| + | === Доказательство === | ||
== Источники == | == Источники == | ||
Версия 12:21, 24 мая 2013
Содержание
Формулировка задачи
Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз.
Решение за O(n)
Обобщение на случай поиска элемента, встречающегося N/K раз
"Хитрое" решение
Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает за
