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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за O(n))
м (Псевдокод)
Строка 9: Строка 9:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
 +
  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
  
 
=== Доказательство ===
 
=== Доказательство ===

Версия 13:46, 24 мая 2013

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

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

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

Обобщение на случай поиска элемента, встречающегося 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].

Источники