多数元素

GitHub跳转原题关系图返回列表

Boyer-Moore 投票：计数器抵消非多数元素，最终留下的候选即为多数。

OJ: leetcodecn

题目 ID: majority-element

难度:普及-

标签:技巧投票算法

日期: 2026-07-29 13:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

找出出现次数超过 n/2 的元素（保证存在）。

思路

Boyer-Moore 投票：维护候选 cand 和计数 cnt。遇到相同则 cnt++，不同则 cnt--，cnt 为 0 时换候选。多数元素数量超过一半，抵消后必然留下。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int> &nums) {
        int cand = 0, cnt = 0;
        for (int x : nums) {
            if (cnt == 0)
                cand = x;
            cnt += (x == cand) ? 1 : -1;
        }
        return cand;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().majorityElement(a) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand = cnt = 0
        for x in nums:
            if cnt == 0:
                cand = x
            cnt += 1 if x == cand else -1
        return cand


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().majorityElement(a))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)。

总结

Boyer-Moore 投票的核心：多数元素数量超过一半，即使所有非多数元素都来抵消，多数元素仍会留下。正确性依赖多数元素存在的前提。