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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 4 участников)
Строка 1: Строка 1:
== Формулировка задачи ==
+
{{Задача
 
+
|definition = Требуется в массиве длиной <tex>N</tex> найти элемент, встречающийся более <tex>N/2</tex> раз. Гарантируется, что такой элемент существует.
Требуется в массиве длиной <tex>N</tex> найти элемент, встречающийся более <tex>N/2</tex> раз. Гарантируется, что такой элемент существует.
+
}}
  
 
== Решение за O(N) ==
 
== Решение за O(N) ==
Строка 7: Строка 7:
 
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
 
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
  
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе - уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
+
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
  
   findMajorityElement(a, N)
+
   '''function''' findMajorityElement(a: '''int[N]'''): '''int'''
     count = 0 // количество людей, оставшихся стоять
+
     count = 0 ''<font color="green">// количество людей, оставшихся стоять</font>''
 
     candidate = <tex>\varnothing</tex>
 
     candidate = <tex>\varnothing</tex>
   
 
 
     '''for''' i = 0 '''to''' N - 1
 
     '''for''' i = 0 '''to''' N - 1
 
       '''if''' count == 0 ''<font color="green">// никто не стоит</font>''
 
       '''if''' count == 0 ''<font color="green">// никто не стоит</font>''
Строка 24: Строка 23:
 
         '''else''' ''<font color="green"> // стоит другой элемент => подобрали пару</font>''
 
         '''else''' ''<font color="green"> // стоит другой элемент => подобрали пару</font>''
 
           count-- ''<font color="green">// уменьшим количество стоящих</font>''
 
           count-- ''<font color="green">// уменьшим количество стоящих</font>''
   
+
    '''return''' candidate
    '''return''' candidate
 
  
 
=== Доказательство ===
 
=== Доказательство ===
  
На <tex>i-</tex>''ом'' шаге выполняется следующий инвариант: если <tex>count > 0</tex>, то <tex>candidate</tex> - мажорирующий элемент на подмассиве <tex>a[0..i]</tex>, либо мажорирующего элемента на данном подмассиве не существует; если <tex>count = 0</tex>, то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на <tex>N</tex>''-ом'' шаге <tex>count</tex> не равно <tex>0</tex> и <tex>candidate</tex> содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.
+
На <tex>i</tex>''-ом'' шаге выполняется следующий инвариант: если <tex>\mathtt{count} > 0</tex>, то <tex>\mathtt{candidate}</tex> мажорирующий элемент на подмассиве <tex>a[0\ldots i]</tex>, либо мажорирующего элемента на данном подмассиве не существует; если <tex>\mathtt{count} = 0</tex>, то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на <tex>N</tex>''-ом'' шаге <tex>\mathtt{count} \ne 0</tex> и <tex>\mathtt{candidate}</tex> содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.
  
Пусть данный инвариант выполняется на <tex>k-</tex>''ом'' шаге. Тогда на <tex>(k+1)-</tex>''ом'' шаге возможны 3 варианта:
+
Пусть данный инвариант выполняется на <tex>k</tex>''-ом'' шаге. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны 3 варианта:
# <tex>count = 0</tex><p>Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
+
# <tex>\mathtt{count} = 0</tex><p>Очевидно, что на подмассиве <tex>a[0\ldots k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
# <tex>count > 0</tex> и <tex>a[k+1] = candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>candidate</tex>.</p>
+
# <tex>\mathtt{count} > 0</tex> и <tex>a[k+1] = \mathtt{candidate}</tex><p>Если на подмассиве <tex>a[0\ldots k]</tex> существует мажорирующий элемент, то он находится в <tex>\mathtt{candidate}</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>\mathtt{candidate}</tex>, если на подмассиве <tex>a[0\ldots k+1]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>\mathtt{candidate}</tex>.</p>
# <tex>count > 0</tex> и <tex>a[k+1] != candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу неравенства <tex>a[k+1]</tex> и <tex>candidate</tex>, образовалась новая пара. Если <tex>count</tex> не станет равным нулю, то, опять же, мажорирующим элементом может быть только <tex>candidate</tex>, так как для всех остальных мы нашли пару, а, значит, встречаются они не более <tex>N/2</tex> раз.</p>
+
# <tex>\mathtt{count} > 0</tex> и <tex>a[k+1] \ne \mathtt{candidate}</tex><p>Если на подмассиве <tex>a[0\ldots k]</tex> существует мажорирующий элемент, то он находится в <tex>\mathtt{candidate}</tex>. Тогда, в силу неравенства <tex>a[k+1]</tex> и <tex>\mathtt{candidate}</tex>, образовалась новая пара. Если <tex>\mathtt{count}</tex> не станет равным нулю, то, опять же, мажорирующим элементом может быть только <tex>\mathtt{candidate}</tex>, так как для всех остальных мы нашли пару, а, значит, встречаются они не более <tex>N/2</tex> раз.</p>
  
  
Строка 46: Строка 44:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
   findMajorityElement(a, N, K)
+
   '''function''' findMajorityElement(a: '''int[N]''', K: '''int'''): '''int[N]'''
  ''<font color="green"> // candidates - словарь, где ключ - стоящий элемент,</font>''
+
    ''<font color="green">//candidates словарь, где ключ стоящий элемент,</font>''
  ''<font color="green"> // значение - количество таких стоящих элементов</font>''
+
    ''<font color="green">//значение количество таких стоящих элементов</font>''
 
     '''for''' i = 0 '''to''' N - 1
 
     '''for''' i = 0 '''to''' N - 1
 
       '''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент</font>''
 
       '''if''' candidates.containsKey(a[i]) ''<font color="green">// нашли стоящий элемент</font>''
 
         candidates[a[i]]++ ''<font color="green">// увеличим счетчик</font>''
 
         candidates[a[i]]++ ''<font color="green">// увеличим счетчик</font>''
 
       '''else'''
 
       '''else'''
         '''if''' candidates.size() < K - 1 ''<font color="green">// полная группа не образована</font>''
+
         '''if''' candidates.size < K - 1 ''<font color="green">// полная группа не образована</font>''
 
           candidates[a[i]] = 1 ''<font color="green">// добавим элемент в группу</font>''
 
           candidates[a[i]] = 1 ''<font color="green">// добавим элемент в группу</font>''
 
         '''else''' ''<font color="green">// образовалась полная группа</font>''
 
         '''else''' ''<font color="green">// образовалась полная группа</font>''
Строка 75: Строка 73:
  
 
=== Доказательство ===
 
=== Доказательство ===
На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0..i]</tex> существуют элементы, которые встречаются больше, чем <tex>i / K</tex> раз, то все они содержатся в <tex>candidates</tex> и размер <tex>candidates</tex> не превышает <tex>K</tex>. Тогда на <tex>N</tex>''-ом'' шаге <tex>candidates</tex> будет содержать все возможные элементы, встречающиеся более, чем <tex>N / K</tex> раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:
+
На <tex>i</tex>''-ом'' шаге поддерживается следующий инвариант: если на подмассиве <tex>a[0\ldots i]</tex> существуют элементы, которые встречаются больше, чем <tex>i / K</tex> раз, то все они содержатся в <tex>\mathtt{candidates}</tex> и размер <tex>\mathtt{candidates}</tex> не превышает <tex>K</tex>. Тогда на <tex>N</tex>''-ом'' шаге <tex>\mathtt{candidates}</tex> будет содержать все возможные элементы, встречающиеся более, чем <tex>N / K</tex> раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:
  
 
Пусть данный инвариант выполняется на <tex>k</tex>''-ом'' шаге. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны <tex>3</tex> варианта:
 
Пусть данный инвариант выполняется на <tex>k</tex>''-ом'' шаге. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны <tex>3</tex> варианта:
#<tex>a[k + 1] \in candidates</tex><p>Размер <tex>candidates</tex> не увеличен, текущий элемент останется стоять. Инвариант выполняется.</p>
+
#<tex>a[k + 1] \in \mathtt{candidates}</tex><p>Размер <tex>\mathtt{candidates}</tex> не увеличен, текущий элемент останется стоять. Инвариант выполняется.</p>
#<tex>a[k + 1] \notin candidates</tex> и <tex>|candidates|() < K - 1</tex><p>Размер <tex>candidates</tex> останется меньше <tex>K</tex>, текущей элемент останется стоять. Инвариант выполняется.</p>
+
#<tex>a[k + 1] \notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates}| < K - 1</tex><p>Размер <tex>\mathtt{candidates}</tex> останется меньше <tex>K</tex>, текущей элемент останется стоять. Инвариант выполняется.</p>
#<tex>a[k + 1] \notin candidates</tex> и <tex>|candidates|() = K - 1</tex><p>Размер <tex>candidates</tex> на данном шаге может только уменьшиться. Сажаем группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем <tex>(k + 1) / K</tex> раз, т.к. мы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из candidates ни к чему плохому не приведет. Инвариант выполняется.</p>
+
#<tex>a[k + 1] \notin \mathtt{candidates}</tex> и <tex>|\mathtt{candidates}| = K - 1</tex><p>Размер <tex>\mathtt{candidates}</tex> на данном шаге может только уменьшиться. Сажаем группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем <tex>(k + 1) / K</tex> раз, т.к. мы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из <tex>\mathtt{candidates}</tex> ни к чему плохому не приведет. Инвариант выполняется.</p>
  
 
Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более <tex>1</tex> увеличения счетчика. Тогда, за все время, происходит не более <tex>N</tex> увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более <tex>2N</tex> обращений к словарю. Следовательно, сложность одной итерации составляет <tex>O(1)</tex>.
 
Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более <tex>1</tex> увеличения счетчика. Тогда, за все время, происходит не более <tex>N</tex> увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более <tex>2N</tex> обращений к словарю. Следовательно, сложность одной итерации составляет <tex>O(1)</tex>.
Строка 93: Строка 91:
  
  
  findMajorityElement(a, N, K)
+
  '''function''' findMajorityElement(a: '''int[N]''', K: '''int'''): '''int'''
   '''while''' true
+
   '''while''' ''true''
 
     candidate = a[random(N)]
 
     candidate = a[random(N)]
 
     count = 0
 
     count = 0
Строка 107: Строка 105:
 
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> проверок. Итоговая сложность <tex>O(N \cdot K)</tex>.
 
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> проверок. Итоговая сложность <tex>O(N \cdot K)</tex>.
  
== Источники информации==
+
== Источники информации ==
  
* [http://habrahabr.ru/post/167177/ Habrahabr - Поиск часто встречающихся элементов в массиве]
+
* [http://habrahabr.ru/post/167177/ Habrahabr Поиск часто встречающихся элементов в массиве]
* [http://algolist.ncstu.ru/olimp/poi_sol.php#a15 Algolist - Решение задачи 15]
+
* [http://algolist.ncstu.ru/olimp/poi_sol.php#a15 Algolist Решение задачи 15]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]

Текущая версия на 19:05, 4 сентября 2022

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


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

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

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

Псевдокод

 function findMajorityElement(a: int[N]): int
   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]\mathtt{count} \gt 0[/math], то [math]\mathtt{candidate}[/math] — мажорирующий элемент на подмассиве [math]a[0\ldots i][/math], либо мажорирующего элемента на данном подмассиве не существует; если [math]\mathtt{count} = 0[/math], то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на [math]N[/math]-ом шаге [math]\mathtt{count} \ne 0[/math] и [math]\mathtt{candidate}[/math] содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.

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

  1. [math]\mathtt{count} = 0[/math]

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

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

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

  3. [math]\mathtt{count} \gt 0[/math] и [math]a[k+1] \ne \mathtt{candidate}[/math]

    Если на подмассиве [math]a[0\ldots k][/math] существует мажорирующий элемент, то он находится в [math]\mathtt{candidate}[/math]. Тогда, в силу неравенства [math]a[k+1][/math] и [math]\mathtt{candidate}[/math], образовалась новая пара. Если [math]\mathtt{count}[/math] не станет равным нулю, то, опять же, мажорирующим элементом может быть только [math]\mathtt{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] раз.

Псевдокод

 function findMajorityElement(a: int[N], K: int): int[N]
   //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\ldots i][/math] существуют элементы, которые встречаются больше, чем [math]i / K[/math] раз, то все они содержатся в [math]\mathtt{candidates}[/math] и размер [math]\mathtt{candidates}[/math] не превышает [math]K[/math]. Тогда на [math]N[/math]-ом шаге [math]\mathtt{candidates}[/math] будет содержать все возможные элементы, встречающиеся более, чем [math]N / K[/math] раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:

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

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

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

  2. [math]a[k + 1] \notin \mathtt{candidates}[/math] и [math]|\mathtt{candidates}| \lt K - 1[/math]

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

  3. [math]a[k + 1] \notin \mathtt{candidates}[/math] и [math]|\mathtt{candidates}| = K - 1[/math]

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

Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более [math]1[/math] увеличения счетчика. Тогда, за все время, происходит не более [math]N[/math] увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более [math]2N[/math] обращений к словарю. Следовательно, сложность одной итерации составляет [math]O(1)[/math].

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

Альтернативное решение

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

Псевдокод

function findMajorityElement(a: int[N], K: int): int
  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].

Источники информации