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

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

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

Решение за O(n)

Алгоритм можно представить следующим образом: пусть на вечеринке собрались [math]N[/math] людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они садятся. В конце концов останутся стоять только гости с одинаковыми элементами. Это и есть искомый элемент.

Псевдокод

 findMajorityElement(a, N)
   count = 0 // количество людей, оставшихся стоять
   candidate = null
   
   for i = 0 to N - 1
     if count == 0
       candidate = a[i]
       count++
     else
       if a[i] == candidate
         count++
       else
         count--
    
    return candidate

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

Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем [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

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

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

Источники

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