多数元素 图解题解

这道题真正在问什么

给长度为 n 的数组，题目保证其中有一个元素出现次数超过 ⌊n/2⌋（严格过半），要求把它找出来。「保证存在」和「严格过半」是决定解法的两个前提：过半意味着这个元素比其余所有元素加起来还多，这份悬殊的差距正是后面投票抵消法的底气。

哈希计数和排序为什么不是最优

用哈希表数每个元素的出现次数，O(n) 时间就能找到答案，但要 O(n) 空间；排序后取中间位置的数也一定是多数元素（它过半，无论怎么排都会覆盖中点），但排序要 O(n log n)。当面试官追问「能不能 O(n) 时间加 O(1) 空间」时，这两条路都被堵死——需要一种只用常数个变量、扫一遍就能锁定多数派的办法，摩尔投票（Boyer-Moore 投票算法）就是为此而生。

摩尔投票：不同的数互相抵消

投票法的直觉是打擂台：让一个非多数元素和一个多数元素配对同归于尽，两边各消耗一个。多数元素比其余全部加起来还多，哪怕每个「杂牌」都精准地拉一个多数元素垫背，多数元素也必有剩余。落到代码上只要两个变量：cand 是当前押注的候选人，count 是它的净胜票——遇到相同的数票数加一，遇到不同的数票数减一，减到零说明前面这段完全打平，就换当前数当新候选、票数重置为一。

为什么最后站住的候选一定是答案

把数组按「count 归零的时刻」切成若干段，每个打平的段内部恰好完全抵消，而任何一段里多数元素至多占一半。它在全数组严格过半，被各段抵消掉的部分凑不够它的总数，所以最后必然剩下一段消不平、且盈余的是多数元素——它就是收尾时的 cand。反过来，如果题目不保证多数元素存在，这条推理的前提就塌了：最后的 cand 只是嫌疑人，必须再扫一遍数它的真实出现次数，确认是否真的过半。

复杂度与两个容易写错的点

时间 O(n)：数组扫一遍，每个元素只做一次比较和一次加减。空间 O(1)：全程只有 cand 和 count 两个变量，不开哈希表。实现上最常见的错：一是 count 归零时忘了换候选人，投票链条直接断掉；二是把「同票加一、异票减一」写反，候选人会被自己人抵消、被对手抬轿，结果完全错乱。

Python

def majorityElement(nums):
    cand = None
    count = 0                      # 候选人票数
    for x in nums:
        if count == 0:             # 没人了，换候选人
            cand = x
            count = 1
        elif x == cand:            # 同票 +1
            count += 1
        else:                      # 异票 -1
            count -= 1
    return cand

C++

int majorityElement(vector<int>& nums){
    int cand = 0, count = 0;
    for (int x : nums) {
        if (count == 0) { cand = x; count = 1; }
        else if (x == cand) count++;
        else count--;
    }
    return cand;
}

Java

public int majorityElement(int[] nums) {
    int cand = 0, count = 0;
    for (int x : nums) {
        if (count == 0) { cand = x; count = 1; }
        else if (x == cand) count++;
        else count--;
    }
    return cand;
}