Мажорирующий элемент

Формулировка задачи

Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз.

"Хитрое" решение

Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем [math]N / K[/math] раз. Будем делать так, пока не найдем нужный элемент. Утверждается, что данный алгоритм в среднем работает за [math]O(N \cdot K)[/math]

Псевдокод

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

Доказательство

Источники

• Habrahabr - Поиск часто встречающихся элементов в массиве
• Algolist - Решение задачи 15