会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
多数元素出现次数严格大于 ⌊n/2⌋，题目还保证它一定存在，所以不必处理「没有多数」的情况。
- 最直接的做法是用哈希表统计每个数出现几次，找出次数大于 ⌊n/2⌋ 的那个。n≤5×104，这样做时间和空间都是 O(n)，可以通过。
- 更省空间的做法是 Boyer-Moore 投票：维护当前候选人 cand 和它的票数 cnt。遇到 cand 就 cnt+1，遇到别的就 cnt−1；票数掉到 0 时，把当前数立成新的候选人。
- 不同的数会互相抵消。因为多数元素的出现次数过半，抵消完之后留下的候选人一定是它。题目保证存在，所以扫一遍即可，不用再验票。
- 也可以排序后取下标 ⌊n/2⌋ 上的元素，复杂度 O(nlogn)。
- 常见假解：直接输出第一个数（它不一定是多数）；只统计正数，漏掉负数多数元素。
