13
правок
Изменения
Нет описания правки
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе <tex>- </tex> уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
=== Псевдокод ===
=== Доказательство ===
На <tex>i-</tex>''-ом'' шаге выполняется следующий инвариант: если <tex>count > 0</tex>, то <tex>candidate-</tex> - мажорирующий элемент на подмассиве <tex>a[0..i]</tex>, либо мажорирующего элемента на данном подмассиве не существует; если <tex>count = 0</tex>, то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на <tex>N</tex>''-ом'' шаге <tex>count</tex> не равно <tex>0</tex> и <tex>candidate</tex> содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.
Пусть данный инвариант выполняется на <tex>k-</tex>''-ом'' шаге. Тогда на <tex>(k+1)-</tex>''-ом'' шаге возможны 3 варианта:
# <tex>count = 0</tex><p>Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
# <tex>count > 0</tex> и <tex>a[k+1] = candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>candidate</tex>.</p>
findMajorityElement(a, N, K)
''<font color="green"> // <tex>candidates - </tex> словарь, где <ключ <tex>- </tex> стоящий элемент,</font>'' ''<font color="green"> // значение <tex>- </tex> количество таких стоящих элементов</font>''
'''for''' i = 0 '''to''' N - 1
'''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент</font>''
== Источники информации==
* [http://habrahabr.ru/post/167177/ Habrahabr <tex>- </tex> Поиск часто встречающихся элементов в массиве]* [http://algolist.ncstu.ru/olimp/poi_sol.php#a15 Algolist <tex>- </tex> Решение задачи 15]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
