多数派要素：Boyer-Moore投票法
線形時間・O(1)空間のBoyer-Moore投票アルゴリズムを使ってn/2回より多く出現する要素を見つけ、その正しさを証明します。
「多数派要素：Boyer-Moore投票法」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
過半数要素の問題
過半数要素 (LeetCode 169): 長さ n の配列で、n/2 回を超えて出現する要素を見つけます。問題の保証により、過半数要素は必ず存在します。[3, 2, 3] の答えは 3 です。[2, 2, 1, 1, 1, 2, 2] の答えは 2 です（7個中4回出現します）。アプローチには、O(n log n) のソートから、洗練された O(n)・O(1) の Boyer-Moore 投票アルゴリズムまであります。
# 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())})')Boyer-Moore 以前のアプローチ
最適解に至るまでの3つのアプローチを見てみましょう。(1) ソート: 配列をソートします。中央の要素は常に過半数要素です（>n/2 回出現するためです）。計算量は O(n log n)、空間計算量は O(1) です。(2) ハッシュマップ: 出現頻度を数え、count が > n/2 となる要素を返します。計算量は O(n)、空間計算量は O(n) です。(3) ランダムサンプリング: 要素をランダムに1つ選び、それが >n/2 回出現することを確認します。期待試行回数は O(1) です（過半数要素が選ばれる確率は >1/2 です）。Boyer-Moore は、決定的に 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)) # 2Boyer-Moore 投票アルゴリズム
Boyer-Moore 投票アルゴリズムは、candidate と count を管理します。配列を順に走査し、count == 0 なら現在の要素を新しい candidate に設定します。現在の要素が candidate と一致する場合は count を増やし、一致しない場合は count を減らします。最後に残った candidate が過半数要素です。これは、過半数要素の出現回数が他のすべての要素の合計より多く、投票によって完全に除外されることがないため成り立ちます。
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アルゴリズムの直感的な理解
直感的には、各要素が異なる要素の出現を1つ「相殺」すると考えます。過半数要素（count > n/2）は、他のすべての要素の合計より多く出現するため、過半数要素以外の要素をすべて相殺しても、なお出現が残ります。count 変数は、現在の candidate の正味の優勢を追跡します。count が 0 になったとき、現在の candidate は同数の反対要素によって相殺されています。次に現れる要素が新しい candidate になります。
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 を、出現回数が k > n/2 である過半数要素とします。アルゴリズムの終了時に、過半数要素以外の要素が candidate になる可能性はあるでしょうか。そのためには、m が完全に相殺されていなければなりません。m を1回相殺するには、別の要素の出現が1回必要です。m の k 回の出現をすべて相殺するには、m 以外の要素が少なくとも k 回出現する必要があります。しかし k > n/2 であり、m 以外の要素の合計は 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 回を超えて出現するすべての要素を見つけます。この条件を満たせる要素は最大2つです（3 × n/3 = n であるためです）。Boyer-Moore を拡張し、2つの候補と2つの count を管理します。新しい要素がどちらの候補とも一致せず、両方の count が正の場合は、両方を減らします。最後に検証のための走査を行い、実際に 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]一般化 Boyer-Moore: n/k 超の多数要素
Boyer-Moore は、k-1 個の候補を使うことで、n/k 回を超えて出現するすべての要素を見つけるよう一般化できます。この条件を満たせる要素は最大 k-1 個です。k-1 個の (candidate, count) ペアを管理します。一致する候補がなく、すべての count が正の場合は、すべての count を1減らします。この一般化アルゴリズムは O(n) 時間、O(k) 空間で実行されます。面接では、通常、2候補を使う 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)分割統治による過半数要素
D&C によるアプローチでは、配列を半分に分割します。配列全体の過半数要素は、少なくとも片方の半分で過半数になっていなければなりません（どちらの半分でも過半数でなければ、全体で 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])) # 2Boyer-Moore と他の手法の比較
過半数要素に対する手法を比較します。ソート: O(n log n) 時間、O(1) 空間、破壊的です。ハッシュマップ: O(n) 時間、O(n) 空間、非破壊的です。D&C: O(n log n) 時間、呼び出しスタックに O(log n) の空間を使います。Boyer-Moore: O(n) 時間、O(1) 空間、1回の走査、非破壊的です。この問題では、Boyer-Moore が他の手法より明確に優れています。面接では、より簡単なハッシュマップのアプローチに簡単に触れたうえで、必ず Boyer-Moore から説明を始めてください。
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}')過半数の存在が保証されない場合
Boyer-Moore は常に candidate を返しますが、過半数要素が存在しない場合、それが過半数要素であるとは限りません。問題で過半数要素の存在が保証されていない場合は、検証が必要です。Boyer-Moore の後で candidate の出現回数を数えます。count が > n/2 なら、それが過半数要素です。そうでなければ -1 または None を返します。この検証により O(n) の走査がもう1回必要になりますが、アルゴリズム全体の計算量は 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) の解法として Boyer-Moore を紹介します。(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)')クイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念の理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Boyer-Moore 投票アルゴリズムにより、candidate と count を使って過半数要素以外の要素を相殺しながら、O(n) 時間、O(1) 空間で過半数要素を見つけられること、このアルゴリズムは2つの候補を使うことで n/3 の過半数要素にも拡張でき、過半数要素が保証されない場合は検証の走査が必要になること、そして証明は、過半数要素の出現回数が他のすべての要素の合計より多く、完全に相殺されることがないという事実に基づいていることを学びました。次は、分割境界に対する二分探索を使って、2つのソート済み配列の中央値に取り組みます。
よくある質問
「多数派要素：Boyer-Moore投票法」レッスンは無料ですか？
はい。「多数派要素：Boyer-Moore投票法」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「多数派要素：Boyer-Moore投票法」で何を学びますか？
線形時間・O(1)空間のBoyer-Moore投票アルゴリズムを使ってn/2回より多く出現する要素を見つけ、その正しさを証明します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「多数派要素：Boyer-Moore投票法」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 分割統治のテンプレート
- 変更版マージソートで転倒数を数える
- 多数派要素：Boyer-Moore投票法
- 2つのソート済み配列の中央値