60
правок
Изменения
Нет описания правки
{{Задача|definition == Формулировка задачи == Требуется в массиве длиной <tex>N</tex> найти элемент, встречающийся более <tex>N/2</tex> раз. Гарантируется, что такой элемент существует.}}
== Решение за O(N) ==
=== Псевдокод ===
'''function''' findMajorityElement(a: '''int*[N]''', N: '''int'''): '''int'''
count = 0 ''<font color="green">// количество людей, оставшихся стоять</font>''
candidate = <tex>\varnothing</tex>
=== Псевдокод ===
'''function''' findMajorityElement(a: '''int*[N]''', N: '''int''', K: '''int'''): '''int*[N]'''
''<font color="green">//candidates — словарь, где ключ — стоящий элемент,</font>''
''<font color="green">//значение — количество таких стоящих элементов</font>''
'''function''' findMajorityElement(a: '''int*[N]''', N: '''int''', K: '''int'''): '''int'''
'''while''' ''true''
candidate = a[random(N)]
