7.2. Поиск доминирующего элемента

Ваша задача — проверить, содержит ли данная последовательность элемент, который встречается более половины раз.

• Формат ввода: Первая строка содержит целое число $n$, следующая — последовательность $n$ целых неотрицательных чисел $a_0, \dotsc, a_{n-1}$.
• Формат вывода: Выведите $1$, если в последовательности содержится элемент, который встречается больше, чем $n/2$ раз, и $0$ в противном случае.
• Ограничения: $1 \le n \le 10^5$; $0 \le a_i \le 10^9$ для всех $0 \le i < n$.
• Примеры:

Пример 1

Пример 2

• В первом примере $2$ — доминирующий элемент.
• Во втором примере у последовательности нет доминирующего элемента. Обратите внимание, что элемент $1$ — не доминирующий.

Решение

Здесь приведён примитивный алгоритм, который решает задачу «Поиск доминирующего элемента» за квадратичное время:

MajorityElement(A[1..n]):
    for i from 1 to n:
        currentElement = A[i]
        count = 0
        for j from 1 to n:
            if A[j] = currentElement:
                count = count + 1
        if count > n/2:
            return 1
    return 0

На практике входную последовательность можно просканировать и сохранить число вхождений каждого элемента в ассоциативном массиве. Время выполнения этого решения зависит от конкретной реализации ассоциативного массива. Если реализация представляет собой сбалансированное дерево поиска, тогда каждый уточняющий запрос в массиве занимает $O(\log n)$, а общее время выполнения составляет $O(n\log n)$. Для хеш-таблиц уточняющие запросы эффективны на практике, хотя и могут варьироваться в зависимости от вводных данных.

Стратегия «разделяй и властвуй» приводит к простому алгоритму с временем выполнения $O(n \log n)$. Несложная, но невероятно важная вещь: если $e$ — это доминирующий элемент последовательности, тогда $e$ должен быть доминирующим элементом как минимум в одной из половин. Однако обратите внимание, что обратное неверно: обе половины последовательности $(2, 3, 3, 7, 5, 7)$ содержат доминирующие элементы ($3$ и $7$ соответственно), но ни один из них не является доминирующим элементом изначальной последовательности. Это приводит нас к следующему алгоритму: найти доминирующий элемент в обоих половинах с помощью рекурсии и для каждой из половин проверить количество вхождений в изначальную последовательность. Для последнего шага нам необходимо ещё раз сделать линейное сканирование, что может занять время $O(n)$. Следовательно, время выполнения $T(n)$ удовлетворяет $T(n) \le 2T(n/2)+O(n)$, поэтому $T(n)=O(n\log n)$.

✒️ Упражнение:
Сможете ли вы спроектировать еще более быстрый алгоритм с временем выполнения $O(n)$? В основе лежит следующая идея. Разделить вводные элементы на пары. Рассмотреть каждую пару: если два элемента различны, отбросить оба; в противном случае отбросить один из них.