Изменения

{{Задача|definition == Формулировка задачи == Требуется в массиве длиной <tex>N</tex> найти элемент, встречающийся более <tex>N/2</tex> раз. Гарантируется, что такой элемент существует.}}

Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе - — уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.

'''function''' findMajorityElement(a, : '''int[N]'''): '''int''' count = 0 ''<font color="green">// количество людей, оставшихся стоять</font>''

'''if''' count == 0 ''<font color="green">// никто не стоит</font>'' candidate = a[i] ''<font color="green">// встанет текущий элемент</font>'' count++ ''<font color="green">// увеличим количество стоящих</font>'' '''else''' ''<font color="green">// кто-то стоит</font>'' '''if''' a[i] == candidate ''<font color="green">// стоит такой же элемент</font>'' count++ ''<font color="green">// увеличим количество стоящих</font>'' '''else''' ''<font color="green"> // стоит другой элемент => подобрали пару</font>'' count-- ''<font color="green">// уменьшим количество стоящих</font>'' '''return''' candidate

На <tex>i-</tex>''-ом'' шаге выполняется следующий инвариант: если <tex>\mathtt{count } > 0</tex>, то <tex>\mathtt{candidate}</tex> - — мажорирующий элемент на подмассиве <tex>a[0..\ldots i]</tex>, либо мажорирующего элемента на данном подмассиве не существует; если <tex>\mathtt{count } = 0</tex>, то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на <tex>N</tex>''-ом'' шаге <tex>\mathtt{count</tex> не равно <tex>} \ne 0</tex> и <tex>\mathtt{candidate}</tex> содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.

Пусть данный инвариант выполняется на <tex>k-</tex>''-ом'' шаге. Тогда на <tex>(k+1)-</tex>''-ом'' шаге возможны 3 варианта:# <tex>\mathtt{count } = 0</tex><p>Очевидно, что на подмассиве <tex>a[0..\ldots k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p># <tex>\mathtt{count } > 0</tex> и <tex>a[k+1] = \mathtt{candidate}</tex><p>Если на подмассиве <tex>a[0..\ldots k]</tex> существует мажорирующий элемент, то он находится в <tex>\mathtt{candidate}</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>\mathtt{candidate}</tex>, если на подмассиве <tex>a[0..(\ldots k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>\mathtt{candidate}</tex>.</p># <tex>\mathtt{count } > 0</tex> и <tex>a[k+1] != \ne \mathtt{candidate}</tex><p>Если на подмассиве <tex>a[0..\ldots k]</tex> существует мажорирующий элемент, то он находится в <tex>\mathtt{candidate}</tex>. Тогда, в силу неравенства <tex>a[k+1]</tex> и <tex>\mathtt{candidate}</tex>, образовалась новая пара. Если <tex>\mathtt{count}</tex> не станет равным нулю, то, опять же, мажорирующим элементом может быть только <tex>\mathtt{candidate}</tex>, так как для всех остальных мы нашли пару, а, значит, встречаются они не более <tex>N/2</tex> раз.</p>

Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы садили сажали людей парами, а теперь будем садить сажать группами из <tex>K</tex> человек. В итоге, если искомые нами элементы есть, то они останутся стоять.

Будем идти по массиву и хранить элементы, которые еще не сели. При встрече элемента, который уже есть среди стоящих, увеличиваем счетчик данного элемента на <tex>1</tex>. В противном случае смотрим, можем ли мы посадить группу и, либо ее садимсажаем, либо добавляем текущий элемент к стоящим. В конце требуется сделать проверку, что оставшиеся стоять элементы встречаются <tex>N/K</tex> раз.

'''function''' findMajorityElement(a, : '''int[N]''', K: '''int'''): '''int[N]''' ''<font color="green">// candidates - — словарь, где ключ - — стоящий элемент,</font>'' ''<font color="green">// значение - — количество таких стоящих элементов</font>''

'''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент</font>'' candidates[a[i]]++ ''<font color="green">// увеличим счетчик</font>''

'''if''' candidates.size() < K - 1 ''<font color="green">// полная группа не образована</font>'' candidates[a[i]] = 1 ''<font color="green">// добавим элемент в группу</font>'' '''else''' ''<font color="green">// образовалась полная группа</font>'' '''for''' element '''in''' candidates ''<font color="green">// посадим группу</font>''

'''if''' candidates[element] == 0 ''<font color="green">// если никто с таким элементом не стоит</font>'' candidates.remove(element) ''<font color="green">// удалим этот элемент</font>''

'''for''' candidate '''in''' candidates ''<font color="green">// обнулим счетчик</font>''

'''for''' i = 0 '''to''' N - 1 ''<font color="green">// посчитаем, сколько раз встречаются элементы</font>''

'''for''' candidate '''in''' candidates ''<font color="green">// проверим, встречается ли элемент N / K раз</font>''

На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0..\ldots i]</tex> существуют элементы, которые встречаются больше, чем <tex>N i / K</tex> раз, то все они содержатся в <tex>\mathtt{candidates}</tex> и размер <tex>\mathtt{candidates}</tex> не превышает <tex>K</tex>. Тогда на <tex>N</tex>''-ом'' шаге шаге <tex>\mathtt{candidates}</tex> будет содержать все возможные элементы, встречающиеся более, чем <tex>N / K</tex> раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:

#<tex>a[k + 1] \in \mathtt{candidates}</tex><p>Размер <tex>\mathtt{candidates}</tex> не увеличен, текущий элемент останется стоять. Инвариант выполняется.</p>#<tex>a[k + 1] \notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates.size() }| < K - 1</tex><p>Размер <tex>\mathtt{candidates}</tex> останется меньше <tex>K</tex>, текущей элемент останется стоять. Инвариант выполняется.</p>#<tex>a[k + 1] \notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates.size() }| = K - 1</tex><p>Размер <tex>\mathtt{candidates}</tex> на данном шаге может только уменьшиться. Садим Сажаем группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем <tex>(k + 1) / K</tex> раз, т.к. мы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из <tex>\mathtt{candidates }</tex> ни к чему плохому не приведет. Инвариант выполняется.</p> Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более <tex>1</tex> увеличения счетчика. Тогда, за все время, происходит не более <tex>N</tex> увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более <tex>2N</tex> обращений к словарю. Следовательно, сложность одной итерации составляет <tex>O(1)</tex>.

Каждая Получается, при реализации словаря на основе хэш-таблиц, каждая итерация в среднем выполняется за <tex>O(1) при реализации словаря на основе хэш-таблиц</tex>. Итоговая сложность <tex>O(N) </tex> с дополнительной памятью <tex>O(K)</tex>.

'''function''' findMajorityElement(a, : '''int[N]''', K: '''int'''): '''int''' '''while''''' true''

== Источники информации ==

* [http://habrahabr.ru/post/167177/ Habrahabr - — Поиск часто встречающихся элементов в массиве]* [http://algolist.ncstu.ru/olimp/poi_sol.php#a15 Algolist - — Решение задачи 15]