Голосование Бойера-Мура: как найти элемент большинства за O(n) и O(1) памяти

Коротко

• Идея: элементы с разными значениями сокращаются парами. Если какое-то значение занимает больше половины массива, на все его копии пар не хватит, и оно останется последним.
• Главная ловушка: алгоритм выдаёт только кандидата. Если большинство не гарантировано, нужен второй проход с настоящим подсчётом.
• Обобщение: для порога $n/3$ достаточно двух кандидатов, для $n/k$ — $k-1$ кандидата.

Это не тот Бойер-Мур

Роберт Бойер и Джей Стротер Мур придумали два разных алгоритма, и оба часто называют просто «алгоритмом Бойера-Мура».

• Поиск подстроки (1977) — ищет образец в тексте и прыгает вперёд по таблицам смещений. Там строки, эвристики плохого символа и хорошего суффикса.
• Голосование (техотчёт 1981 года) — ищет значение, которое занимает больше половины массива. Здесь два числа и один цикл.

Общего у них только авторы. Эта статья про голосование. Если на собеседовании вас просят найти подстроку, вам нужна другая тема, например алгоритм КМП.

Задача

Дан массив nums длины n. Элемент большинства (majority element) встречается строго больше $n/2$ раз.

[2, 2, 1, 1, 1, 2, 2]  → 2 (4 раза из 7)
[3, 2, 3]              → 3 (2 раза из 3)
[1, 1, 2, 2]           → нет: у обоих значений ровно половина
[1, 2, 3]              → нет: все встречаются по разу

Большинство — не то же самое, что самый частый элемент. В [1, 1, 2, 3, 4] чаще всех встречается единица, но она занимает 2 места из 5, поэтому большинства здесь нет. Это различие ещё всплывёт в разделе про ошибки.

В классической постановке (LeetCode 169, у нас — Majority Element) большинство гарантировано. На реальном собеседовании эту гарантию могут убрать, поэтому про неё стоит спросить сразу.

Решение 1: словарь

Первое, что приходит в голову, и это нормальный первый ответ: посчитать частоты хеш-таблицей.

from collections import Counter


def majority_dict(nums):
    for value, freq in Counter(nums).items():
        if freq > len(nums) // 2:
            return value
    return None

Время $O(n)$ в среднем, память $O(n)$ в худшем случае: например, если большинства нет и все элементы разные. Заодно этот код честно отвечает None, когда большинства нет.

Запись freq > len(nums) // 2 эквивалентна строгому «больше $n/2$» и для нечётных n: при $n = 5$ порог равен 2, и условие требует минимум трёх вхождений, как и нужно.

Решение 2: сортировка

Если значение занимает больше половины массива, то после сортировки его блок обязательно накрывает середину. Слева от индекса n // 2 всего n // 2 ячеек, справа ещё меньше или столько же, а длина блока больше половины. Целиком уместиться с одной стороны он не может.

def majority_sort(nums):
    return sorted(nums)[len(nums) // 2]

индексы:  0  1  2  3  4  5  6
sorted:   1  1  1  2  2  2  2
                   ↑
                 n // 2 = 3

Одна строка, но есть две оговорки.

Память. sorted делает копию на $O(n)$. nums.sort() меняет входной массив, и Timsort всё равно может занять временный буфер до $n/2$ элементов. Константная память возможна только при in-place сортировке вроде пирамидальной.

Гарантия. Без большинства этот код всё равно что-нибудь вернёт: на [1, 2, 3] получим двойку. Результат придётся проверять отдельным проходом.

Время здесь $O(n \log n)$. Оценка хуже, чем у словаря, зато решение хорошо показывает, что вы заметили структуру задачи. Подробнее про такие оценки — в статье про Big O.

Решение 3: счётчик вместо словаря

Теперь избавимся от памяти. Заведём одну переменную-кандидата и один счётчик:

def majority_candidate(nums):
    candidate = None
    count = 0

    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1

    return candidate

Правила такие:

1. Счётчик равен нулю — текущий элемент становится новым кандидатом.
2. Элемент совпал с кандидатом — счётчик растёт.
3. Не совпал — счётчик падает.

Прогоним на [2, 2, 1, 1, 1, 2, 2]:

Ответ — двойка. Обратите внимание на две вещи: на пятом шаге кандидатом временно была единица, а итоговый count равен 1, хотя двойка встречается 4 раза. Счётчик — это не частота, это только остаток после сокращений.

Сложность: один проход, $O(n)$ по времени и $O(1)$ по памяти.

Почему сокращение пар работает

Обычно это объясняют метафорой про армии: солдаты разных сторон гибнут один за одного, и выживает самая большая сторона. Звучит убедительно, но сразу возникает вопрос: а если сокращаются два элемента, ни один из которых не относится к большинству? Разберём без метафор.

Инвариант. После каждого шага все просмотренные элементы можно разбить на две группы:

• count свободных копий текущего candidate;
• пары из двух разных значений.

Проверим по веткам кода:

• count == 0, свободных копий нет. Новый x становится единственной свободной копией нового кандидата.
• x == candidate. Появляется ещё одна свободная копия.
• x != candidate. Берём одну свободную копию кандидата и образуем с x пару. Значения в ней разные, инвариант держится.

На нашем примере выходят пары (2, 1), (2, 1), (1, 2) и одна свободная двойка. Всего $3 \cdot 2 + 1 = 7$ элементов.

Доказательство. Пусть m — настоящий элемент большинства, а алгоритм закончил с другим кандидатом. Тогда свободных копий m нет, и все его вхождения лежат в парах. В каждой паре значения разные, значит, m встречается в ней максимум один раз. Получаем:

Это противоречит условию $\text{freq}(m) > n/2$. Значит, кандидат равен m.

Теперь ответ на вопрос про пары без m. Пара вроде (1, 3) не мешает, а помогает: она тратит два элемента и ни одной копии большинства. Самый неудобный для m случай — каждая его копия в паре с чужим значением, но и тогда чужих элементов не хватит на все копии.

Здесь же видно, почему нужно именно строго больше половины. Если у значения ровно $n/2$ вхождений, чужих элементов хватит на все его копии: в [1, 2, 3, 1] единицы уходят в пары (1, 2) и (3, 1), и кандидатом остаётся тройка.

Второй проход: когда он обязателен

Доказательство работает только в одну сторону: если большинство есть, кандидат равен ему. Обратное неверно. Алгоритм всегда кого-нибудь вернёт:

print(majority_candidate([1, 2, 3]))        # 3
print(majority_candidate([1, 1, 2, 2, 3]))  # 3, хотя тройка встречается один раз
print(majority_candidate([1, 1, 2, 3, 4]))  # 4, хотя чаще всех встречается 1

Поэтому, если гарантии нет, кандидата нужно проверить настоящим подсчётом:

def find_majority(nums):
    candidate = majority_candidate(nums)
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None


print(find_majority([2, 2, 1, 1, 1, 2, 2]))  # 2
print(find_majority([1, 2, 3]))              # None
print(find_majority([]))                     # None

Время остаётся $O(n)$, память — $O(1)$. Пустой массив тоже обрабатывается: кандидат будет None, его вхождений 0, а условие 0 > 0 ложно.

Можно ли обойтись одним проходом? В общем случае нет. Для потоковых данных известен результат: алгоритм с сублинейной памятью не может за один проход определить, есть ли большинство. Если данные идут потоком, который нельзя перечитать, вы получите только кандидата, а подтверждать его придётся другим способом.

Majority Element II: порог n/3

Задача (LeetCode 229): найти все значения, которые встречаются строго больше $n/3$ раз. Гарантий здесь нет.

Таких значений максимум два: три значения с частотой выше $n/3$ заняли бы больше n ячеек. Значит, хватит двух кандидатов и двух счётчиков. Вместо пар теперь сокращаются тройки разных значений.

def majority_elements(nums):
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    for x in nums:
        if x == candidate1:
            count1 += 1
        elif x == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = x, 1
        elif count2 == 0:
            candidate2, count2 = x, 1
        else:
            count1 -= 1
            count2 -= 1

    threshold = len(nums) // 3
    return [
        c
        for c in (candidate1, candidate2)
        if c is not None and nums.count(c) > threshold
    ]


print(majority_elements([3, 2, 3]))                 # [3]
print(majority_elements([1, 1, 1, 2, 2, 3, 3, 3]))  # [1, 3]
print(majority_elements([1, 2, 3, 4]))              # []

Логика доказательства та же. Просмотренные элементы делятся на свободные копии двух кандидатов и тройки из трёх разных значений. Последняя ветка else и есть такая тройка: копия первого кандидата, копия второго и x.

Если значение m с частотой больше $n/3$ не попало в кандидаты, все его копии лежат в тройках, по одной на тройку. Тогда троек больше $n/3$, а элементов в них больше n. Противоречие.

Счётчики и здесь не равны частотам. На [1, 1, 1, 2, 2, 3, 3, 3] алгоритм заканчивает с count1 = 1 и count2 = 1, а настоящие частоты обоих кандидатов равны 3. Поэтому второй проход здесь обязателен всегда: на [1, 2, 3, 4] кандидаты есть, а ответа нет.

Общий случай: алгоритм Мисры-Гриса

Для порога $n/k$ нужно $k-1$ счётчиков. Это алгоритм Мисры и Гриса (1982), он же Misra-Gries summary. Хранить счётчики удобно в словаре, размер которого не превысит $k-1$:

def frequent_elements(nums, k):
    counters = {}

    for x in nums:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k - 1:
            counters[x] = 1
        else:
            for key in list(counters):
                counters[key] -= 1
                if counters[key] == 0:
                    del counters[key]

    freq = dict.fromkeys(counters, 0)
    for x in nums:
        if x in freq:
            freq[x] += 1

    return [x for x, f in freq.items() if f > len(nums) // k]


print(frequent_elements([2, 2, 1, 1, 1, 2, 2], 2))                 # [2]
print(frequent_elements([1, 1, 1, 2, 2, 3, 3, 3], 3))              # [1, 3]
print(frequent_elements([1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 5, 6], 4))  # [1, 2]

При k = 2 это обычное голосование, при k = 3 — решение из прошлого раздела.

Внутренний цикл не портит оценку. Каждый его запуск стоит $O(k)$, но снимает $k-1$ единиц, накопленных раньше, а всего единиц накапливается не больше n. Итого $O(n)$ по времени в среднем и $O(k)$ по памяти.

Полезное следствие: каждое сокращение убирает $k$ разных элементов, поэтому их не больше $n/k$. Значит, счётчик после первого прохода занижает настоящую частоту максимум на $n/k$. На этом свойстве основан поиск популярных значений в потоках данных (heavy hitters), когда перечитать данные нельзя, а приблизительной оценки хватает. Если данные лежат в памяти и нужны $k$ самых частых значений, а не значения выше порога, это другая задача — Top K Frequent.

Другие решения за линейное время

Могут спросить «а как ещё?». Вот что можно назвать, если большинство гарантировано.

По битам. В каждом разряде бит элемента большинства побеждает: его копии занимают больше половины массива. Собираем ответ из победивших битов (подробнее про битовые операции).

def majority_bits(nums):
    result = 0
    for bit in range(32):
        ones = sum((x >> bit) & 1 for x in nums)
        if ones > len(nums) // 2:
            result |= 1 << bit
    return result - (1 << 32) if result >= 1 << 31 else result


print(majority_bits([3, 2, 3]))            # 3
print(majority_bits([-3, -3, 5, -3, 7]))   # -3

Это $O(32 \cdot n)$ и $O(1)$ памяти, но только для чисел и только с фиксированной разрядностью. Без гарантии код может вернуть значение, которого вообще нет в массиве: на [3, 5, 6] получится 7.

Quickselect. Элемент большинства всегда стоит на месте медианы, поэтому достаточно найти элемент с индексом n // 2. В среднем $O(n)$, в худшем $O(n^2)$, и массив при этом меняется.

Случайный выбор. Берём случайный элемент и считаем его вхождения. С вероятностью больше $1/2$ мы сразу попали в большинство, так что в среднем нужно меньше двух попыток. Без гарантии такой цикл может не завершиться, поэтому число попыток надо ограничивать, а ответ в этом случае становится вероятностным.

Типичные ошибки

Нет второго прохода. Самая частая ошибка: решение скопировано из задачи с гарантией и применено там, где гарантии нет.

Нестрогое сравнение. Условие count >= n // 2 пропустит единицу в [1, 1, 2, 3], хотя она занимает ровно половину. Нужно >.

Итоговый count как частота. На примере из таблицы он равен 1, а двойка встречается 4 раза. Настоящую частоту даёт только второй проход.

count > 0 как признак большинства. Вывод работает только в одну сторону. count == 0 действительно означает, что большинства нет: все элементы разбились на пары. Но count > 0 ничего не доказывает, на [1, 2, 3] он равен 1.

Голосование для поиска моды. Алгоритм не ищет самый частый элемент. На [1, 1, 2, 3, 4] он вернёт четвёрку, а чаще всех встречается единица. Для моды нужен словарь.

Проверка результата как булева значения. Если в массиве есть ноль, if find_majority(nums): примет найденный ноль за отсутствие ответа. Сравнивайте с None явно.

Генератор вместо списка. Второй проход по итератору ничего не увидит:

stream = (x for x in [3, 2, 3])
candidate = majority_candidate(stream)
print(sum(1 for x in stream if x == candidate))  # 0: генератор уже исчерпан

Неверный порядок условий в версии n/3. Сначала сравниваем x с кандидатами и только потом проверяем нулевые счётчики. Если поменять их местами, одно значение займёт оба слота:

def majority_elements_wrong(nums):
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    for x in nums:
        if count1 == 0:  # ошибка: проверка нуля раньше сравнения
            candidate1, count1 = x, 1
        elif count2 == 0:
            candidate2, count2 = x, 1
        elif x == candidate1:
            count1 += 1
        elif x == candidate2:
            count2 += 1
        else:
            count1 -= 1
            count2 -= 1

    threshold = len(nums) // 3
    return [
        c
        for c in (candidate1, candidate2)
        if c is not None and nums.count(c) > threshold
    ]


print(majority_elements_wrong([1, 2, 3, 2, 2]))           # [2, 2]
print(majority_elements_wrong([1, 1, 1, 3, 1, 4, 2, 3]))  # [], хотя единица встречается 4 раза из 8

Первый вывод — просто дубль. Второй хуже: из-за занятых обоих слотов одна и та же единица теряет сразу две копии за сокращение и выпадает из кандидатов.

Значение None как кандидат. В n/3 проверка c is not None отсекает незаполненные слоты. Если в массиве может встретиться сам None, нужен отдельный маркер, например object().

На собеседовании

Задача встречается в наборах для подготовки как лёгкая, а в оригинальной постановке LeetCode 169 просит подумать о решении за линейное время и $O(1)$ памяти. Настоящая проверка часто начинается после первого рабочего кода.

Порядок, который хорошо работает:

1. Уточните условие. Гарантировано ли большинство? Порог строгий? Можно ли менять массив?
2. Назовите словарь. $O(n)$ времени и памяти, короткий код.
3. Скажите про сортировку. Покажите, что блок накрывает середину.
4. Перейдите к голосованию и сразу объясните инвариант про пары, а не просто запишите код.
5. Сами проговорите второй проход, даже если он сейчас не нужен: «при наличии гарантии проверка не требуется, а без неё я бы добавил подсчёт».

Последний пункт стоит многого: так вы показываете, что понимаете границы применимости алгоритма. Как вести такой разговор вслух, разобрано в статье про рассуждения на собеседовании.

Частые продолжения:

• Порог $n/3$. Два кандидата и обязательный второй проход (LeetCode 229).
• Порог $n/k$. Мисра-Грис, $O(n)$ времени и $O(k)$ памяти.
• Данные потоком. За один проход получаем только кандидата, подтверждение требует либо второго прохода, либо намного большей памяти.
• Большинство на подмассиве. LeetCode 2780 (Minimum Index of a Valid Split) сводится к поиску доминирующего элемента и линейному проходу. LeetCode 1157 (Online Majority Element In Subarray) — уже сложная задача на запросы.

Для тренировки решите Majority Element без словаря, затем напишите find_majority с проверкой и добавьте версию для $n/3$. Похожие приёмы собраны в подборке задач на массивы.