174
правки
Изменения
→Решение за O(n)
Требуется в массиве длиной ''N'' найти элемент, встречающийся более ''N/2'' раз. Гарантируется, что такой элемент существует.
== Решение за O(nN) ==
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только гости с одинаковыми элементами. Это и есть искомый элемент.
Всего происходит <tex>N</tex> итераций, каждая из которых обрабатывается за <tex>O(1)</tex>. Итоговая асимптотика <tex>O(nN)</tex>.
== Обобщение на случай поиска элемента, встречающегося N/K раз ==
