Ваша задача — проверить, содержит ли данная последовательность элемент, который встречается более половины раз.
- Формат ввода: Первая строка содержит целое число $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
Ввод | Вывод |
---|---|
5 2 3 9 2 2 | 1 |
Пример 2
Ввод | Вывод |
---|---|
4 1 2 3 1 | 0 |
- В первом примере $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)$? В основе лежит следующая идея. Разделить вводные элементы на пары. Рассмотреть каждую пару: если два элемента различны, отбросить оба; в противном случае отбросить один из них.