Мажорирующий элемент — различия между версиями
(→"Хитрое" решение) |
Никита (обсуждение | вклад) (→Псевдокод) |
||
| Строка 13: | Строка 13: | ||
=== Псевдокод === | === Псевдокод === | ||
| + | |||
| + | findMajorityElement(a, N, K) | ||
| + | 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 | ||
=== Доказательство === | === Доказательство === | ||
Версия 12:42, 24 мая 2013
Содержание
Формулировка задачи
Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз.
Решение за O(n)
Обобщение на случай поиска элемента, встречающегося N/K раз
"Хитрое" решение
Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает за
Псевдокод
findMajorityElement(a, N, K)
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
