Мажорирующий элемент
| Задача: |
| Требуется в массиве длиной найти элемент, встречающийся более раз. Гарантируется, что такой элемент существует. |
Решение за O(N)
Алгоритм можно представить следующим образом: пусть на вечеринке собрались людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе — уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
Псевдокод
function findMajorityElement(a: int[N], N: int): int
count = 0 // количество людей, оставшихся стоять
candidate =
for i = 0 to N - 1
if count == 0 // никто не стоит
candidate = a[i] // встанет текущий элемент
count++ // увеличим количество стоящих
else // кто-то стоит
if a[i] == candidate // стоит такой же элемент
count++ // увеличим количество стоящих
else // стоит другой элемент => подобрали пару
count-- // уменьшим количество стоящих
return candidate
Доказательство
На -ом шаге выполняется следующий инвариант: если , то — мажорирующий элемент на подмассиве , либо мажорирующего элемента на данном подмассиве не существует; если , то мажорирующего элемента на данном подмассиве не существует. Нам гарантируется существование мажорирующего элемента, значит на -ом шаге и содержит мажорирующий элемент. Покажем, что данный инвариант всегда выполняется.
Пусть данный инвариант выполняется на -ом шаге. Тогда на -ом шаге возможны 3 варианта:
-
Очевидно, что на подмассиве мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только может быть мажорирующим элементом.
- и
Если на подмассиве существует мажорирующий элемент, то он находится в . Тогда, в силу равенства и , если на подмассиве существует мажорирующий элемент, то он тоже будет равен .
- и
Если на подмассиве существует мажорирующий элемент, то он находится в . Тогда, в силу неравенства и , образовалась новая пара. Если не станет равным нулю, то, опять же, мажорирующим элементом может быть только , так как для всех остальных мы нашли пару, а, значит, встречаются они не более раз.
Всего происходит итераций, каждая из которых обрабатывается за . Итоговая асимптотика .
Обобщение на случай поиска элемента, встречающегося N/K раз
Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы сажали людей парами, а теперь будем сажать группами из человек. В итоге, если искомые нами элементы есть, то они останутся стоять.
Будем идти по массиву и хранить элементы, которые еще не сели. При встрече элемента, который уже есть среди стоящих, увеличиваем счетчик данного элемента на . В противном случае смотрим, можем ли мы посадить группу и, либо ее сажаем, либо добавляем текущий элемент к стоящим. В конце требуется сделать проверку, что оставшиеся стоять элементы встречаются раз.
Псевдокод
function findMajorityElement(a: int[N], N: int, 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
Доказательство
На -ом шаге поддерживается следующий инвариант: если на подмассиве существуют элементы, которые встречаются больше, чем раз, то все они содержатся в и размер не превышает . Тогда на -ом шаге будет содержать все возможные элементы, встречающиеся более, чем раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:
Пусть данный инвариант выполняется на -ом шаге. Тогда на -ом шаге возможны варианта:
Размер не увеличен, текущий элемент останется стоять. Инвариант выполняется.
- и
Размер останется меньше , текущей элемент останется стоять. Инвариант выполняется.
- и
Размер на данном шаге может только уменьшиться. Сажаем группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем раз, т.к. мы могли успеть посадить максимум групп. Тогда удаление данного элемента из ни к чему плохому не приведет. Инвариант выполняется.
Рассмотрим среднее количество обращений к словарю за одну итерацию. На каждой итерации происходит не более увеличения счетчика. Тогда, за все время, происходит не более увеличений. Так как количество уменьшений счетчика не может превышать количество увеличений, то всего происходит не более обращений к словарю. Следовательно, сложность одной итерации составляет .
Получается, при реализации словаря на основе хэш-таблиц, каждая итерация в среднем выполняется за . Итоговая сложность с дополнительной памятью .
Альтернативное решение
Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем раз. Будем делать так, пока не найдем подходящий элемент. Утверждается, что данный алгоритм в среднем работает за
Псевдокод
function findMajorityElement(a: int[N], N: int, 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
Доказательство
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за . Вероятность, что мы выбрали элемент "удачно" составляет . Тогда, в среднем, мы будем делать проверок. Итоговая сложность .
