Элемент большинства: голосование Бойера—Мура
Найдите элемент, встречающийся более n/2 раз, с помощью линейного алгоритма голосования Бойера—Мура с O(1) дополнительной памятью и докажите его корректность
«Элемент большинства: голосование Бойера—Мура» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Задача о мажоритарном элементе
Мажоритарный элемент (LeetCode 169): найдите элемент, который встречается в массиве длины n более n/2 раз. По условию задачи мажоритарный элемент всегда существует. Для [3, 2, 3] ответом будет 3. Для [2, 2, 1, 1, 1, 2, 2] ответом будет 2: он встречается 4 раза из 7. Подходы варьируются от сортировки за O(n log n) до элегантного детерминированного алгоритма голосования Бойера—Мура за O(n) времени и O(1) памяти.
# The majority element appears MORE than n/2 times
# So it appears more than all other elements COMBINED
examples = [
[3, 2, 3], # 3 appears 2/3 times > 1/2
[2, 2, 1, 1, 1, 2, 2], # 2 appears 4/7 times > 3.5
[1], # trivially 1
[1, 1, 2, 1], # 1 appears 3/4 times
]
for e in examples:
from collections import Counter
c = Counter(e)
print(f'Array: {e} → majority: {max(c, key=c.get)} (count {max(c.values())})')Подходы до алгоритма Бойера—Мура
Три подхода до оптимального решения: (1) Сортировка: отсортируйте массив; средний элемент всегда будет мажоритарным, поскольку он встречается более чем в половине массива. Сложность — O(n log n), память — O(1). (2) Хеш-таблица: подсчитайте частоты и верните элемент с количеством вхождений > n/2. Сложность по времени — O(n), по памяти — O(n). (3) Случайная выборка: выберите случайный элемент и проверьте, встречается ли он более чем n/2 раз; ожидаемое число попыток равно O(1), поскольку мажоритарный элемент выбирается с вероятностью >1/2. Алгоритм голосования Бойера—Мура достигает сложности O(n) по времени и O(1) по памяти детерминированно.
from collections import Counter
def majority_sort(nums):
nums.sort()
return nums[len(nums) // 2] # middle is always majority
def majority_hashmap(nums):
count = Counter(nums)
return max(count, key=count.get)
def majority_random(nums):
import random
n = len(nums)
while True:
candidate = random.choice(nums)
if nums.count(candidate) > n // 2:
return candidate
nums = [2, 2, 1, 1, 1, 2, 2]
print(majority_sort(nums[:])) # 2
print(majority_hashmap(nums)) # 2Алгоритм голосования Бойера—Мура
Алгоритм голосования Бойера—Мура поддерживает candidate и count. Пройдите по массиву: если count == 0, назначьте текущий элемент новым кандидатом. Если текущий элемент совпадает с кандидатом, увеличьте count. В противном случае уменьшите count. В конце кандидат является мажоритарным элементом. Это работает потому, что мажоритарный элемент встречается чаще, чем все остальные элементы вместе взятые, поэтому его невозможно полностью исключить голосованием.
def majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num # new candidate
if num == candidate:
count += 1
else:
count -= 1
return candidate
print(majority_element([3, 2, 3])) # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 2
print(majority_element([1])) # 1Интуиция алгоритма
Интуиция такова: представьте, что каждое вхождение элемента «нейтрализует» одно вхождение другого элемента. У мажоритарного элемента (количество вхождений > n/2) больше вхождений, чем у всех остальных элементов вместе, поэтому он может нейтрализовать все немажоритарные элементы и сохранить часть своих вхождений. Переменная count отслеживает чистое преимущество текущего кандидата. Когда count становится равным 0, текущий кандидат нейтрализован таким же количеством противоположных элементов — следующий появившийся элемент становится новым кандидатом.
def bm_trace(nums):
candidate = count = 0
for i, num in enumerate(nums):
if count == 0:
candidate = num
old_count = count
if num == candidate: count += 1
else: count -= 1
print(f'num={num}: candidate={candidate}, count: {old_count}→{count}')
return candidate
bm_trace([2, 2, 1, 1, 1, 2, 2])
# 2→c=1, 2→c=2, 1→c=1, 1→c=0, 1→new cand=1 c=1, 2→c=0, 2→new cand=2 c=1Доказательство корректности
Доказательство: пусть m — мажоритарный элемент с count, равным k > n/2. Может ли в конце алгоритма кандидатом оказаться немажоритарный элемент? Для этого m должен быть полностью нейтрализован. Каждая нейтрализация m требует одного вхождения некоторого другого элемента. Чтобы нейтрализовать все k вхождений m, необходимо как минимум k вхождений элементов, не равных m. Но k > n/2, а общее число остальных элементов равно n-k < n/2 < k. Получаем противоречие: m не может быть полностью нейтрализован.
# Proof by contradiction visualised:
# Array: [M, M, M, A, B, A, B] (M is majority, 4/7 times)
# Cancellations: M-A, M-B, M-A, M-B would need 4 non-M elements
# But there are only 4 non-M elements and 4 M's > n/2 = 3.5
# So M can survive: after cancellations, at least 1 M remains uncancelled
def verify_bm(tests):
for nums in tests:
result = majority_element(nums)
brute = max(set(nums), key=nums.count)
assert result == brute, f'Mismatch: {nums} → BM={result}, Brute={brute}'
print('All tests passed!')
def majority_element(nums):
c = cnt = 0
for n in nums:
if cnt == 0: c = n
cnt += 1 if n == c else -1
return c
verify_bm([[1],[3,2,3],[1,1,2,1],[2,2,1,1,1,2,2]])Мажоритарный элемент II: больше n/3
Мажоритарный элемент II (LeetCode 229): найдите все элементы, встречающиеся более n/3 раз. Таких элементов может быть не больше двух, поскольку 3 × n/3 = n. Расширьте алгоритм голосования Бойера—Мура, поддерживая двух кандидатов с двумя счётчиками. Когда новый элемент не совпадает ни с одним кандидатом и оба счётчика положительны, уменьшите оба счётчика. Итоговый проход проверки подтверждает, какие кандидаты действительно встречаются чаще n/3 раз.
def majority_element_ii(nums):
cand1 = cand2 = None
count1 = count2 = 0
for num in nums:
if num == cand1: count1 += 1
elif num == cand2: count2 += 1
elif count1 == 0: cand1, count1 = num, 1
elif count2 == 0: cand2, count2 = num, 1
else:
count1 -= 1
count2 -= 1
# Verify: candidates must exceed n/3
n = len(nums)
return [c for c in [cand1, cand2]
if c is not None and nums.count(c) > n // 3]
print(majority_element_ii([3, 2, 3])) # [3]
print(majority_element_ii([1, 2])) # [1, 2]
print(majority_element_ii([1, 1, 1, 3, 3, 2, 2, 2])) # [1, 2]Обобщённый алгоритм Бойера—Мура: большинство n/k
Алгоритм голосования Бойера—Мура обобщается для поиска всех элементов, встречающихся более n/k раз, с использованием k-1 кандидатов. Этому условию могут удовлетворять не более k-1 элементов. Поддерживайте k-1 пар «кандидат, count». Если ни один кандидат не совпадает с текущим элементом и все значения count положительны, уменьшите все значения count на 1. Этот обобщённый алгоритм работает за O(n) времени и использует O(k) памяти. На собеседовании обычно достаточно знать расширение с двумя кандидатами для случая n/3.
def majority_nk(nums, k):
'''Find all elements appearing more than n/k times.'''
counts = {} # candidate -> count
for num in nums:
counts[num] = counts.get(num, 0) + 1
if len(counts) >= k:
# Remove all candidates by decrementing
new_counts = {c: cnt-1 for c, cnt in counts.items() if cnt > 1}
counts = new_counts
# Verify
threshold = len(nums) // k
return [c for c in counts if nums.count(c) > threshold]
print(majority_nk([1,2,3,1,2,1,2,1], 3)) # [1, 2] (both > 8/3 ≈ 2.67)
print(majority_nk([1,1,1,2,2,3,3,3], 4)) # [1, 3] (both > 8/4 = 2)Мажоритарный элемент методом «разделяй и властвуй»
Подход «разделяй и властвуй»: разделите массив пополам. Мажоритарный элемент всего массива должен быть мажоритарным хотя бы в одной половине: если он не является мажоритарным ни в одной из них, в целом он не может встречаться более n/2 раз. Рекурсивно найдите мажоритарный элемент каждой половины. Если результаты для обеих половин совпадают, это и есть ответ. В противном случае подсчитайте вхождения обоих кандидатов во всём массиве и верните того, у кого вхождений больше. Рекуррентное соотношение: T(n) = 2T(n/2) + O(n) → O(n log n).
def majority_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
left_maj = majority_dc(nums, lo, mid)
right_maj = majority_dc(nums, mid + 1, hi)
if left_maj == right_maj:
return left_maj
# Count both candidates across the sub-range
left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left_maj)
right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right_maj)
return left_maj if left_count > right_count else right_maj
print(majority_dc([3, 2, 3])) # 3
print(majority_dc([2, 2, 1, 1, 1, 2, 2])) # 2Бойер—Мур и другие методы
Сравнение методов для задачи о мажоритарном элементе: Сортировка: O(n log n) по времени, O(1) по памяти, изменяет исходный массив. Хеш-таблица: O(n) по времени, O(n) по памяти, не изменяет исходный массив. Метод «разделяй и властвуй»: O(n log n) по времени, O(log n) памяти для стека вызовов. Бойер—Мур: O(n) по времени, O(1) по памяти, один проход, не изменяет исходный массив. Для этой задачи алгоритм Бойера—Мура строго превосходит остальные подходы. На собеседовании после краткого упоминания более простого подхода с хеш-таблицей всегда начинайте с алгоритма Бойера—Мура.
import time, random
nums = [random.randint(1, 100) for _ in range(500000)]
# Make element 42 the majority
nums = [42] * 300000 + nums[:200000]
random.shuffle(nums)
start = time.time()
from collections import Counter
hm = Counter(nums).most_common(1)[0][0]
print(f'HashMap: {hm} in {time.time()-start:.4f}s')
def bm(nums):
c = cnt = 0
for n in nums:
if cnt == 0: c = n
cnt += 1 if n == c else -1
return c
start = time.time()
result = bm(nums)
print(f'Boyer-Moore: {result} in {time.time()-start:.4f}s')
print(f'Both correct: {hm == result}')Если наличие большинства не гарантировано
Алгоритм голосования Бойера—Мура всегда возвращает кандидата, но если мажоритарного элемента не существует, этот кандидат может им не оказаться. Если задача не гарантирует наличие мажоритарного элемента, необходимо выполнить проверку: после алгоритма Бойера—Мура подсчитайте вхождения кандидата. Если count > n/2, это мажоритарный элемент. В противном случае верните -1 или пустое значение. Эта проверка добавляет ещё один проход O(n), но общая сложность алгоритма остаётся O(n) по времени и O(1) по памяти.
def majority_element_safe(nums):
'''Returns majority element or None if it doesn't exist.'''
# Phase 1: find candidate
candidate = count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# Phase 2: verify
if nums.count(candidate) > len(nums) // 2:
return candidate
return None
print(majority_element_safe([3, 2, 3])) # 3 (majority exists)
print(majority_element_safe([1, 2, 3])) # None (no majority)
print(majority_element_safe([1, 2, 1, 2])) # None (tie, neither > n/2)Разбор решения на собеседовании
Подход к задаче о мажоритарном элементе на собеседовании: (1) упомяните сортировку (O(n log n), O(1)) и хеш-таблицу (O(n), O(n)) как исходные подходы; (2) представьте алгоритм голосования Бойера—Мура как оптимальное решение за O(n) и O(1); (3) объясните идею взаимного исключения: мажоритарный элемент нельзя полностью исключить, потому что его вхождений больше, чем всех остальных вместе; (4) аккуратно напишите решение в 5 строках; (5) обработайте крайний случай: если наличие мажоритарного элемента не гарантировано, добавьте проход проверки. Такая структура демонстрирует системное мышление в условиях ограниченного времени.
# Clean 5-line Boyer-Moore for interviews
def majority_element(nums):
c, cnt = nums[0], 1
for n in nums[1:]:
cnt += (1 if n == c else -1)
if cnt == 0: c, cnt = n, 1
return c
# Verification (if majority not guaranteed)
def majority_with_check(nums):
c = majority_element(nums)
return c if nums.count(c) > len(nums) // 2 else -1
print(majority_element([3, 2, 3])) # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 2
print('Time: O(n), Space: O(1)')Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: алгоритм голосования Бойера—Мура находит мажоритарный элемент за O(n) времени и O(1) памяти, используя кандидата и count, которые взаимно исключают немажоритарные элементы, алгоритм расширяется для большинства n/3 с двумя кандидатами и требует прохода проверки, если наличие большинства не гарантировано, а доказательство опирается на тот факт, что мажоритарный элемент встречается чаще, чем все остальные элементы вместе, поэтому его невозможно полностью нейтрализовать. Далее мы займёмся поиском медианы двух отсортированных массивов с помощью двоичного поиска по границе разбиения.
Часто задаваемые вопросы
Урок «Элемент большинства: голосование Бойера—Мура» бесплатный?
Да — полный текст урока «Элемент большинства: голосование Бойера—Мура» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Элемент большинства: голосование Бойера—Мура»?
Найдите элемент, встречающийся более n/2 раз, с помощью линейного алгоритма голосования Бойера—Мура с O(1) дополнительной памятью и докажите его корректность Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Элемент большинства: голосование Бойера—Мура»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Шаблон «Разделяй и властвуй»
- Подсчёт инверсий с помощью изменённой сортировки слиянием
- Элемент большинства: голосование Бойера—Мура
- Медиана двух отсортированных массивов