3622
правки
Изменения
м
Требуется в массиве длиной ''== Решение за O(N'' найти элемент, встречающийся более ''N/2'' раз. Гарантируется, что такой элемент существует.) ==
== Решение за O(n) ==Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, Будем идти по массиву и каждому из них соответствует один запоминать элемент из массива, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе — уменьшаем. Когда встречаются двое с разными элементамиЕсли все элементы уже имеют пару, то они образуют пару и садятся. В конце концов останутся стоять только гости с одинаковыми элементами. Это и есть искомый элементговорим, что у текущего элемента пары нет.
На Пусть данный инвариант выполняется на <tex>k</tex>''i-ом'' шаге выполняется следующий инвариант. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны <tex>3</tex> варианта: если #<tex>count a[k + 1] \in \mathtt{candidates}</tex><p>Размер <tex> 0\mathtt{candidates}</tex>не увеличен, то текущий элемент останется стоять. Инвариант выполняется.</p>#<tex>candidatea[k + 1] \notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates}| < K - мажорирующий 1</tex><p>Размер <tex>\mathtt{candidates}</tex> останется меньше <tex>K</tex>, текущей элемент на подмассиве останется стоять. Инвариант выполняется.</p>#<tex>a[0..ik + 1]\notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates}| = K - 1</tex><p>Размер <tex>\mathtt{candidates}</tex>, либо мажорирующего элемента на данном подмассиве не существуетшаге может только уменьшиться. Сажаем группу. Тогда Если какой-то элемент был удален на ''N-ом'' текущем шаге , то, значит, он встречался не более, чем <tex>candidate(k + 1) / K</tex> будет содержать мажорирующий элемент на всем массивераз, т.к. гарантируется его существованиемы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из <tex>\mathtt{candidates}</tex> ни к чему плохому не приведет. Покажем, что данный инвариант всегда Инвариант выполняется.</p>
Пусть данный инвариант выполняется на ''k-ом'' шагеРассмотрим среднее количество обращений к словарю за одну итерацию. Тогда на ''(k+1)-ом'' шаге возможны 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>candidateN</tex>увеличений.</p># <tex>count > 0</tex> и <tex>a[k+1] != candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элементТак как количество уменьшений счетчика не может превышать количество увеличений, то он находится в всего происходит не более <tex>candidate2N</tex>обращений к словарю. ТогдаСледовательно, так как сложность одной итерации составляет <tex>a[k+O(1])</tex> и <tex>candidate</tex> не равны, то мы нашли новую пару. Если <tex>count</tex> не станет равным нулю, то опять же мажорирующим элементом может быть только candidate, так как для всех остальных мы нашли пару, а значит они встречаются не более <tex>N/2</tex> раз.</p>
== Обобщение Получается, при реализации словаря на случай поиска элементаоснове хэш-таблиц, встречающегося каждая итерация в среднем выполняется за <tex>O(1)</tex>. Итоговая сложность <tex>O(N)</tex> с дополнительной памятью <tex>O(K раз ==)</tex>.
→Псевдокод
{{Задача|definition == Формулировка задачи ==Требуется в массиве длиной <tex>N</tex> найти элемент, встречающийся более <tex>N/2</tex> раз. Гарантируется, что такой элемент существует.}}
=== Псевдокод ===
'''function''' findMajorityElement(a, : '''int[N]'''): '''int''' count = 0 ''<font color="green">// количество людей, оставшихся стоять</font>'' candidate = <tex>\varnothing</tex> '''for''' i = 0 '''to''' N - 1 '''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} \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] = null\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>N</tex> итераций, каждая из которых обрабатывается за <tex>O(1)</tex>. Итоговая асимптотика <tex>O(N)</tex>. == Обобщение на случай поиска элемента, встречающегося N/K раз ==Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы сажали людей парами, а теперь будем сажать группами из <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>'' '''for''' i = 0 '''to''' N - 1 '''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент</font>'' candidates[a[i]]++ ''<font color="green">// увеличим счетчик</font>'' '''else''' '''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>'' candidates[element]-- '''if''' candidates[element] == 0 ''<font color="green">// если никто с таким элементом не стоит</font>'' candidates.remove(element) ''<font color="green">// удалим этот элемент</font>''
'''for ''' candidate '''in''' candidates ''<font color="green">// обнулим счетчик</font>'' candidates[candidate] = 0 '''for''' i = 0 '''to ''' N - 1 if count ''<font color== 0 "green">//посчитаем, сколько раз встречаются элементы</ никто не стоитfont>'' candidate = '''if''' candidates.containsKey(a[i] // встанет текущий элемент) countcandidates[a[i]]++ // увеличим количество стоящих else // кто-то стоит if a[i] '''for''' candidate '''in''' candidates ''<font color== candidate "green">// стоит такой же проверим, встречается ли элемент count++ N /K раз</ увеличим количество стоящихfont>'' else / '''if''' candidates[candidate] > N / стоит другой элемент => подобрали паруK count-- // уменьшим количество стоящих elements.add(candidate) '''return candidate''' elements
=== Доказательство ===
На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0\ldots i]</tex> существуют элементы, которые встречаются больше, чем <tex>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>N / K</tex> раз. Будем делать так, пока не найдем подходящий элемент. Утверждается, что данный алгоритм в среднем работает за <tex>O(N \cdot K)</tex>
'''function''' findMajorityElement(a, : '''int[N]''', K: '''int'''): '''int''' '''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
=== Доказательство ===
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> проверок. Итоговая сложность <tex>O(N \cdot K)</tex>.
== Источники информации ==
* [http://algolist.ncstuhabrahabr.ru/olimppost/167177/poi_sol.php#a15 Habrahabr - — Поиск часто встречающихся элементов в массиве]* [http://algolist.ncstu.ru/olimp/poi_sol.php#a15 Algolist - — Решение задачи 15]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
