> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/169.-majority-element.md).

# 169. Majority Element

math

Given an array `nums` of size `n`, return *the majority element*.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

 

**Example 1:**

<pre><code><strong>Input: nums = [3,2,3]
</strong><strong>Output: 3
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,2,1,1,1,2,2]
</strong><strong>Output: 2
</strong></code></pre>

&#x20;

**Constraints:**

* `n == nums.length`
* `1 <= n <= 5 * 10`<sup>`4`</sup>
* `-10`<sup>`9`</sup>` ``<= nums[i] <= 10`<sup>`9`</sup>

&#x20;

**Follow-up:** Could you solve the problem in linear time and in `O(1)` space?

#### 分析：

#### Boyer-Moore算法原理

直觉上：\
**如果一个元素超过一半，那么"抵消掉"其他元素，它还会剩下来。**

步骤：

1. 一开始没有候选人（candidate），票数是0。
2. 遍历数组：
   * 如果票数是0，选当前元素作为新的候选人。
   * 如果当前元素==候选人，票数+1。
   * 如果当前元素≠候选人，票数-1。
3. 遍历完后，手上拿着的candidate，可能就是多数元素。
4. 最后**验证**一下，真的出现了超过n/2次吗？如果是，返回candidate；否则返回-1。

```
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

```