Мажорирующий элемент
Формулировка задачи
Требуется в массиве длиной найти элемент, встречающийся более раз. Гарантируется, что такой элемент существует.
Решение за O(N)
Алгоритм можно представить следующим образом: пусть на вечеринке собрались людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только люди с одинаковыми элементами. Это и есть искомый элемент.
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе - уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
Псевдокод
findMajorityElement(a, N)
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 раз
Будем пользоваться той же идеей, что и в предыдущем пункте. До этого мы садили людей парами, а теперь будем садить группами из человек. В итоге, если искомые нами элементы есть, то они останутся стоять.
Будем идти по массиву и хранить элементы, которые еще не сели. При встрече элемента, который уже есть среди стоящих, увеличиваем счетчик данного элемента на . В противном случае смотрим, можем ли мы посадить группу и, либо ее садим, либо добавляем текущий элемент к стоящим. В конце требуется сделать проверку, что оставшиеся стоять элементы встречаются раз.
Псевдокод
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
Доказательство
На -ом шаге поддерживается следующий инвариант: если на подмассиве существуют элементы, которые встречаются больше, чем раз, то все они содержатся в и размер не превышает . Тогда на -ом шаге шаге будет содержать все возможные элементы, встречающиеся более, чем раз, остается только выполнить проверку. Покажем, что данный инвариант всегда выполняется:
Пусть данный инвариант выполняется на -ом шаге. Тогда на -ом шаге возможны варианта:
Размер не увеличен, текущий элемент останется стоять. Инвариант выполняется.
- и
Размер останется меньше , текущей элемент останется стоять. Инвариант выполняется.
- и
Размер на данном шаге может только уменьшиться. Садим группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем раз, т.к. мы могли успеть посадить максимум групп. Тогда удаление данного элемента из candidates ни к чему плохому не приведет. Инвариант выполняется.
Каждая итерация в среднем выполняется за O(1) при реализации словаря на основе хэш-таблиц. Итоговая сложность O(N) с дополнительной памятью O(K).
Альтернативное решение
Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем раз. Будем делать так, пока не найдем подходящий элемент. Утверждается, что данный алгоритм в среднем работает за
Псевдокод
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
Доказательство
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за . Вероятность, что мы выбрали элемент "удачно" составляет . Тогда, в среднем, мы будем делать проверок. Итоговая сложность .
