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

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

• Формат ввода: Первая строка содержит целое число , следующая — последовательность целых неотрицательных чисел .
• Формат вывода: Выведите , если в последовательности содержится элемент, который встречается больше, чем раз, и в противном случае.
• Ограничения: ; для всех .
• Примеры:

Пример 1Пример 1

Ввод	Вывод
5 2 3 9 2 2	1

Пример 2Пример 2

Ввод	Вывод
4 1 2 3 1	0

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

РешениеРешение

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

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

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

Стратегия «разделяй и властвуй» приводит к простому алгоритму с временем выполнения . Несложная, но невероятно важная вещь: если — это доминирующий элемент последовательности, тогда должен быть доминирующим элементом как минимум в одной из половин. Однако обратите внимание, что обратное неверно: обе половины последовательности содержат доминирующие элементы ( и соответственно), но ни один из них не является доминирующим элементом изначальной последовательности. Это приводит нас к следующему алгоритму: найти доминирующий элемент в обоих половинах с помощью рекурсии и для каждой из половин проверить количество вхождений в изначальную последовательность. Для последнего шага нам необходимо ещё раз сделать линейное сканирование, что может занять время . Следовательно, время выполнения удовлетворяет , поэтому .

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