Мажорирующий элемент — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за O(N))
м (Обобщение на случай поиска элемента, встречающегося N/K раз)
Строка 40: Строка 40:
  
 
== Обобщение на случай поиска элемента, встречающегося N/K раз ==
 
== Обобщение на случай поиска элемента, встречающегося N/K раз ==
 +
 +
 +
=== Псевдокод ===
 +
 +
 +
=== Доказательство ===
  
 
== "Хитрое" решение ==
 
== "Хитрое" решение ==

Версия 18:53, 24 мая 2013

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

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

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

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

Псевдокод

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

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

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

Источники