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

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

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

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

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

Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе - уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.

Псевдокод

 findMajorityElement(a, N)
   count = 0 // количество людей, оставшихся стоять
   candidate = [math]\varnothing[/math]
   
   for i = 0 to N - 1
     if count == 0 // никто не стоит
       candidate = a[i] // встанет текущий элемент
       count++ // увеличим количество стоящих
     else // кто-то стоит
       if a[i] == candidate // стоит такой же элемент
         count++ // увеличим количество стоящих
       else // стоит другой элемент => подобрали пару
         count-- // уменьшим количество стоящих
    
    return candidate

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

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

Пусть данный инвариант выполняется на [math]k-[/math]ом шаге. Тогда на [math](k+1)-[/math]ом шаге возможны 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] не станет равным нулю, то, опять же, мажорирующим элементом может быть только [math]candidate[/math], так как для всех остальных мы нашли пару, а, значит, встречаются они не более [math]N/2[/math] раз.

Всего происходит [math]N[/math] итераций, каждая из которых обрабатывается за [math]O(1)[/math]. Итоговая асимптотика [math]O(N)[/math].

Обобщение на случай поиска элемента, встречающегося N/K раз

Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы садили людей парами, а теперь будем садить группами из [math]K[/math] человек. В итоге, если искомые нами элементы есть, то они останутся стоять.

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

Псевдокод

 findMajorityElement(a, N, K)
   // candidates - словарь, где ключ - стоящий элемент,
   // значение - количество таких стоящих элементов
   for i = 0 to N - 1
     if candidates.containsKey(a[i]) // нашли стоящий элемент
       candidates[a[i]]++ // увеличим счетчик
     else
       if candidates.size() < K - 1 // полная группа не образована
         candidates[a[i]] = 1 // добавим элемент в группу
       else // образовалась полная группа
         for element in candidates // посадим группу
           candidates[element]--
           if candidates[element] == 0 // если никто с таким элементом не стоит
             candidates.remove(element) // удалим этот элемент
   
   for candidate in candidates // обнулим счетчик
     candidates[candidate] = 0
   
   for i = 0 to N - 1 // посчитаем, сколько раз встречаются элементы
     if candidates.containsKey(a[i])
       candidates[a[i]]++
   
   for candidate in candidates // проверим, встречается ли элемент N / K раз
     if candidates[candidate] > N / K
        elements.add(candidate)
     
   return elements

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

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

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

1. [math]a[k + 1] \in candidates[/math]

   Размер [math]candidates[/math] не увеличен, текущий элемент останется стоять. Инвариант выполняется.

2. [math]a[k + 1] \notin candidates[/math] и [math]candidates.size() \lt K - 1[/math]

   Размер [math]candidates[/math] останется меньше [math]K[/math], текущей элемент останется стоять. Инвариант выполняется.

3. [math]a[k + 1] \notin candidates[/math] и [math]candidates.size() = K - 1[/math]

   Размер [math]candidates[/math] на данном шаге может только уменьшиться. Садим группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем [math](k + 1) / K[/math] раз, т.к. мы могли успеть посадить максимум [math](k + 1) / K[/math] групп. Тогда удаление данного элемента из candidates ни к чему плохому не приведет. Инвариант выполняется.

Пусть операции со словарем выполняются за [math]O(X)[/math]. Тогда покажем, что в среднем итерация выполняется тоже за [math]O(X)[/math]. Заметим, что увеличение счетчика эквивалентно добавлению элемента в [math]candidates[/math], а уменьшение счетчика - удалению элемента. Тогда на кажой итерации происходят добавления или удаления элементов. В рамках одной итерации мы добавляем не более [math]1[/math] элемента. Тогда, количество элементов не превышает [math]N[/math]. Максимум, что мы можем сделать - это добавить [math]N[/math] элементов и их же удалить. Получается [math]O(N)[/math] операций. Всего итераций [math]N[/math] штук. Тогда на каждую итерацию в среднем приходится [math]O(1)[/math] операций и итоговая сложность итерации [math]O(X)[/math].

Получается, при реализации словаря на основе хэш-таблиц, каждая итерация в среднем выполняется за [math]O(1)[/math]. Итоговая сложность [math]O(N)[/math] с дополнительной памятью [math]O(K)[/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