# LeetCode 169. Majority Element
[LeetCode 169. Majority Element](https://leetcode.com/problems/majority-element/) (難度 通過率)
<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code>n == nums.length</code></li>
<li><code>1 <= n <= 5 * 10^4</code></li>
<li><code>-10^9 <= nums[i] <= 10^9</code></li>
</ul>

- Solution
這題要找的是某一個元素量超過陣列長度一半的數。
因為題目有提到要用 O(n) 的時間複雜度及 O(1) 的空間複雜度，所以我參考[這篇](https://ithelp.ithome.com.tw/articles/10213285)的演算法。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int res = nums[0], cnt = 1;
            for (int i = 1; i < nums.size(); i++) {
                if (nums[i] == res)
                    cnt++;
                else if (cnt > 0)
                    cnt--;
                else {
                    res = nums[i];
                    cnt++;
                }
            }
            return res;
        }
    };

- Boyer–Moore 多數投票算法

Boyer–Moore 多數投票算法 （Boyer–Moore Voting Algorithm）是一種用來尋找序列中出現次數超過一半的元素（即「多數元素」）的高效算法。這個算法的主要優勢是時間複雜度為 \(O(n)\)，而空間複雜度為 \(O(1)\)。以下是如何思考和理解這個算法的過程：

### 步驟

1. **初始化**：
- 設定兩個變數，`candidate`（候選者）和 `count`（計數器）。`candidate` 用來存儲目前的候選多數元素，`count` 則用來記錄候選者的出現次數。

2. **第一遍掃描**：
- 遍歷整個序列中的每個元素：
- 如果 `count` 為 0，則將當前元素設為 `candidate`，並將 `count` 設為 1。
- 如果當前元素等於 `candidate`，則 `count` 加 1。
- 如果當前元素不等於 `candidate`，則 `count` 減 1。

這個過程會在候選者中找到一個可能的多數元素，但需要確認這個候選者是否真正是多數元素。

3. **第二遍掃描**（可選）：
- 遍歷整個序列，計算候選者出現的次數，確認它是否超過一半。

### 思考過程

- **理解候選者選擇原理**：
- 當 `count` 為 0 時，新的候選者會被選中。這樣的原因是，`count` 代表目前候選者的「剩餘優勢」，如果 `count` 為 0，表示先前的候選者沒有足夠的支持，需要更新候選者。

- **平衡機制**：
- 當遇到與候選者不同的元素時，`count` 會減少，這會平衡候選者的支持。如果候選者在序列中實際上是多數元素，它會最終佔據超過一半的次數。

- **檢查候選者的多數性**：
- 第一遍掃描確定了候選者，但可能需要第二遍掃描來確認該候選者的出現次數是否超過一半。

### 例子

假設序列是 `[3, 3, 4, 2, 4, 4, 2, 4, 4]`：

1. **第一遍掃描**：
- 初始化 `candidate` 為 `None` 和 `count` 為 0。
- 遍歷序列，選擇候選者 `4`，最後得到 `candidate = 4`。

2. **第二遍掃描**：
- 計算 `4` 出現的次數，發現它超過了序列長度的一半，確認 `4` 是多數元素。

這樣就能確保找到的候選者如果存在多數元素，則一定是正確的。