多数元素：Boyer-Moore 投票法
使用线性时间、O(1) 空间的 Boyer-Moore 投票算法，找出出现次数超过 n/2 的元素，并证明算法的正确性。
多数元素：Boyer-Moore 投票法 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 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（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 之前的方法
在最优方法之前，可以考虑三种方法：(1) 排序：对数组排序；中间元素一定是多数元素（因为它出现了超过 n/2 次）。复杂度为 O(n log n)，空间复杂度为 O(1)。(2) 哈希映射：统计频率，并返回出现次数 > n/2 的元素。时间复杂度为 O(n)，空间复杂度为 O(n)。(3) 随机抽样：随机选择一个元素，并验证它出现次数是否 >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 投票算法维护一个候选元素和一个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 是多数元素，其出现次数为 k > n/2。算法结束时，候选元素可能是非多数元素吗？要出现这种情况，m 必须被完全抵消。每抵消一次 m，都需要消耗某个其他元素的一次出现。要抵消 m 的全部 k 次出现，至少需要 k 次非 m 元素的出现。但 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 扩展为维护两个候选元素及其两个计数。当新元素与两个候选元素都不匹配且两个计数都为正数时，将两个计数同时减一。最后再进行一次验证，以确认哪些候选元素确实超过 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 对（候选元素，计数）。当没有候选元素匹配且所有计数都为正数时，将所有计数减一。该推广算法的时间复杂度为 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])) # 2Boyer-Moore 与其他方法的比较
多数元素问题的方法比较：排序：时间复杂度 O(n log n)，空间复杂度 O(1)，会修改原数组。哈希映射：时间复杂度 O(n)，空间复杂度 O(n)，不会修改原数组。分治法：时间复杂度 O(n log n)，调用栈空间复杂度 O(log n)。Boyer-Moore：时间复杂度 O(n)，空间复杂度 O(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 总会返回一个候选元素，但如果不存在多数元素，该候选元素可能并不是多数元素。如果题目不保证存在多数元素，就必须进行验证：执行 Boyer-Moore 后，统计候选元素的出现次数。如果 count > n/2，它就是多数元素；否则返回 -1 或 None。这次验证会增加一次 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) 介绍 Boyer-Moore，将其作为最优的 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)')快速检查
请检查您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：Boyer-Moore 投票算法使用一个候选元素和一个 count，通过抵消非多数元素，在 O(n) 时间复杂度和 O(1) 空间复杂度下找到多数元素；该算法可以扩展到 n/3 多数元素问题，使用两个候选元素，并且在不保证存在多数元素时需要额外的验证遍历；以及证明依赖于这样一个事实：多数元素的出现次数多于其他所有元素出现次数之和，因此不可能被完全抵消。接下来，我们将使用基于分割边界的二分查找，解决两个有序数组的中位数问题。
常见问题解答
「多数元素：Boyer-Moore 投票法」课时是免费的吗？
是的 — 「多数元素：Boyer-Moore 投票法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「多数元素：Boyer-Moore 投票法」这节课中我会学到什么？
使用线性时间、O(1) 空间的 Boyer-Moore 投票算法，找出出现次数超过 n/2 的元素，并证明算法的正确性。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「多数元素：Boyer-Moore 投票法」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 分治模板
- 使用修改后的归并排序统计逆序对
- 多数元素：Boyer-Moore 投票法
- 两个有序数组的中位数