---
description: "Boyer-Moore 投票：不同的数两两抵消，多数元素超过一半，抵消到最后一定还剩它，O(n) O(1)"
---

# 169. 多数元素

LeetCode 169[^leetcode] · 简单 · 技巧

## 题

给一个长度为 `n` 的数组，其中有一个元素出现次数严格大于 `n / 2`，找出它。进阶要求线性时间、常数空间。

例：`nums = [2, 2, 1, 1, 1, 2, 2]` → `2`。

## 一句话

维护一个候选和票数：遇到同一个数票数 +1，不同 -1，票数归零就换当前数当候选；扫完剩下的候选就是答案。

## 关键技巧

**抵消论证。** 每次「票数 -1」相当于从数组里删掉一对**不同**的数。删掉一对不同的数后，多数元素仍是剩余部分的多数——这一对里至多有一个是它，它的占比不降。一直删到不能再删，剩下的只能全是同一个数，而多数元素不可能被删光（它比其余所有数加起来还多），所以剩下的就是它。

**为什么票数归零时换候选不亏。** 归零意味着目前扫过的前缀已经被两两抵消干净，前缀里任何数都没有超过一半——多数元素在剩余后缀里依然过半，对后缀重新开始投票即可。

**前提很重要。** 投票法只在「保证存在多数元素」时直接返回；不保证时要再扫一遍验证候选的出现次数。

**其他解法对比。** 排序取中位数 $O(n\log n)$；哈希计数 $O(n)$ 空间；按位统计（每一位上多数元素的位值也占多数）$O(32n)$ 时间 $O(1)$ 空间。

## 解

```python
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand, votes = None, 0
        for x in nums:
            if votes == 0:
                cand = x          # 前缀已抵消干净，重新选候选
            votes += 1 if x == cand else -1
        return cand
```

时间 $O(n)$，空间 $O(1)$。

## 延伸

- **超过 n/3 的元素**（LeetCode 229）：至多 2 个，维护两个候选同时投票，最后必须验证。
- **「抵消」的另一种形态**：[136. 只出现一次的数字](0136-single-number.md) 用异或让成对的数自我抵消。
- **中位数视角**：多数元素一定是排序后下标 `n // 2` 的那个——可以用 [215. 数组中的第K个最大元素](0215-kth-largest-element-in-an-array.md) 的快速选择 $O(n)$ 求出。

??? note "自测"

    ```python
    s = Solution()
    assert s.majorityElement([3, 2, 3]) == 3
    assert s.majorityElement([2, 2, 1, 1, 1, 2, 2]) == 2
    assert s.majorityElement([7]) == 7
    assert s.majorityElement([1, 2, 1, 3, 1]) == 1
    ```

[^leetcode]: [LeetCode 169](https://leetcode.cn/problems/majority-element/)，2026-09-29 读。