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