多数元素 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

题意：计算 $nums$ 的绝对众数。绝对众数的出现次数，比其余所有元素的出现次数加起来还多。题目保证 $nums$ 一定存在绝对众数。

尝试设计一个 $O (n)$ 一次遍历，同时只用到 $O (1)$ 额外空间的算法。

想象一众武林高手比武，谁会笑到最后？

我用「擂台赛」打比方：

擂主登场： $nums [0]$ 成为初始擂主，生命值为 $1$ 。
挑战者出现：遍历后续元素，作为挑战者。
比武：如果挑战者与擂主属于同一门派（值相同），那么擂主生命值加 $1$ ，否则擂主生命值减 $1$ 。
擂主更迭：如果比武后，擂主生命值降为 $0$ （同归于尽），那么下一个挑战者成为新的擂主，生命值为 $1$ 。
最后在擂台上的那人，便是武林盟主（绝对众数）。

为什么这样做是对的？

设出现次数最多的元素的出现次数为 $a$ ，其余元素的出现次数之和为 $b = n - a$ 。题目保证 $a > b$ 。

证明：上述过程中，每次擂主的生命值降为 $0$ 时，相当于开了一个新的擂台赛，在 $nums [i - 1]$ 和 $nums [i]$ 之间切一刀。这会把 $nums$ 分成若干段。依次考察这些段：

对于除了最后一段的每一段（注意这些段的擂主不一定是绝对众数，比如绝对众数是 $9$ ，这一段是 $[1, 1, 2, 9]$ ），设绝对众数在其中出现了 $x$ 次，其余元素的出现次数之和为 $y$ ，则必然有 $x \leq y$ 。这可以用反证法证明，如果 $x > y$ ，那么绝对众数血多，不可能被其余元素同归于尽，绝对众数的生命值在这段结束时必然大于 $0$ ，矛盾。由此可得 $a - x > b - y$ ，意思是，把 $a$ 减去 $x$ ， $b$ 减去 $y$ ，所得到的 $a^{'}$ 和 $b^{'}$ 仍然满足 $a^{'} > b^{'}$ 。依此类推，每一段结束时，在剩余元素（未遍历到的元素）中，设出现次数最多的元素的出现次数为 $a^{'}$ ，其余元素的出现次数之和为 $b^{'}$ ，那么 $a^{'} > b^{'}$ 始终成立。
对于最后一段，由于 $a^{'} > b^{'}$ ，绝对众数血多，不可能被其余元素同归于尽，绝对众数的生命值最终必然大于 $0$ ，所以最后在擂台上的是绝对众数。

Python 解法1C++ 解法1

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = hp = 0
        for x in nums:
            if hp == 0:  # x 是初始擂主，生命值为 1
                ans, hp = x, 1
            else:  # 比武，同门加血，否则扣血
                hp += 1 if x == ans else -1
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = 0, hp = 0;
        for (int x : nums) {
            if (hp == 0) { // x 是初始擂主，生命值为 1
                ans = x;
                hp = 1;
            } else { // 比武，同门加血，否则扣血
                hp += x == ans ? 1 : -1;
            }
        }
        return ans;
    }
};