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

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

Требуется в массиве длиной 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

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

На i-ом шаге выполняется следующий инвариант: если [math]count \gt 0[/math], то [math]candidate[/math] - мажорирующий элемент на подмассиве [math]a[0..i][/math], либо мажорирующего элемента на данном подмассиве не существует. Тогда на N-ом шаге [math]candidate[/math] будет содержать мажорирующий элемент на всем массиве, т.к. гарантируется его существование. Покажем, что данный инвариант всегда выполняется.

Пусть данный инвариант выполняется на k-ом шаге. Тогда на (k+1)-ом шаге возможны 3 варианта:

1. [math]count = 0[/math]

   Очевидно, что на подмассиве [math]a[0..k][/math] мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только [math]a[k+1][/math] может быть мажорирующим элементом.

2. [math]count \gt 0[/math] и [math]a[k+1] = candidate[/math]

   Если на подмассиве [math]a[0..k][/math] существует мажорирующий элемент, то он находится в [math]candidate[/math]. Тогда, в силу равенства [math]a[k+1][/math] и [math]candidate[/math], если на подмассиве [math]a[0..(k+1)][/math] существует мажорирующий элемент, то он тоже будет равен [math]candidate[/math].

3. [math]count \gt 0[/math] и [math]a[k+1] != candidate[/math]

   Если на подмассиве [math]a[0..k][/math] существует мажорирующий элемент, то он находится в [math]candidate[/math]. Тогда, в силу неравенства [math]a[k+1][/math] и [math]candidate[/math], образовалась новая пара. Если [math]count[/math] не станет равным нулю, то опять же мажорирующим элементом может быть только candidate, так как для всех остальных мы нашли пару, а значит встречаются они не более [math]N/2[/math] раз.

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

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