參考：LeetCode_多數元素 II 題解

1.概述

（1）摩爾投票法 (Boyer–Moore Majority Vote Algorithm) 是一種用來尋找一組元素中多數元素的常量級空間復雜度算法。一般來說，摩爾投票法常用于求眾數，求眾數這個問題本身比較簡單，但是想要使用常量級空間復雜度來實現卻不是那么簡單。而摩爾投票法正是這樣一種算法。

（2）眾數 (Mode) 是指在統計分布上具有明顯集中趨勢點的數值，代表數據的一般水平。 也是一組數據中出現次數最多的數值，有時眾數在一組數中有好幾個。用 M 表示。上面提到的多數元素與眾數的含義差不多，只不過在摩爾投票法算法中，多數元素是指在數組（長度為 n）中出現次數大于某個閾值 (t) 的元素，并且存在如下結論：

• 如果 t = ?n / 2?，那么多數元素最多只有 1 個；
• 如果 t = ?n / 3?，那么多數元素最多只有 2 個；
• 如果 t = ?n / (m + 1)?，那么多數元素最多只有 m 個；

2.算法思想

（1）摩爾投票法的核心思想為對拼消耗。首先我們考慮最基本的摩爾投票問題，比如找出一組數字序列中出現次數大于 ?n / 2? 的數字（并且假設這個數字一定存在）。我們可以直接利用反證法證明這樣的數字只可能有一個：

• 假設我們當前數組中存在次數大于總數一半的元素為 x，數組的總長度為 n，則我們可以把數組分為兩部分：
  • 一部分為相同的 k 個元素 x；
  • 另一部分為 $\frac{n?k}{2}$ 對個不同的元素配對，
• 此時我們假設還存在另外一個次數大于總數一半的元素 y，則此時 y 因該滿足 y > $\frac{n}{2}$ ，但是按照我們之前的推理 y 應當滿足 y ≤ $\frac{n?k}{2}$ ，二者自相矛盾。

因此，對于 t = ?n / 2?，摩爾投票算法的核心思想是基于這個事實：每次從序列里選擇兩個不相同的數字刪除掉（或稱為抵消），最后剩下一個數字或幾個相同的數字，就是出現次數大于總數一半的那個元素。

（2）對于 t = ?n / 3?，我們可以利用反證法推斷出滿足這樣條件的元素最多只有兩個，同理，我們可以利用摩爾投票法的核心思想，每次選擇三個互不相同的元素進行刪除（或稱為「抵消」），推導思路如下：

• 假設數組中一定只存在一個次數大于 ?$\frac{n}{3}$? 的元素 x，則此時我們可以把數組分成兩部分：一部分相同的 k 個元素 x，另一部分為 $\frac{n?k}{3}$ 組三個不同的元素，我們知道三個不同的元素會被抵消，因此最終只會剩下一個元素為 x。
• 如果只存在 2 個次數大于 ?$\frac{n}{3}$? 的元素時，假設這兩個不同的元素分別為 x 和 y，則此時我們一定可以把數組分成三部分：第一部分相同的 m 個元素 x，第二部分相同的 k 個元素 y，第三部分為 $\frac{n?m?k}{3}$ 組三個互不同的元素，我們知道三個互不同的元素會被抵消，因此最終只會剩下兩個元素為 x 和 y。

具體思路如下：

• 我們每次檢測當前元素是否為第一個選中的元素或者第二個選中的元素；
• 每次我們發現當前元素與已經選中的兩個元素都不相同，則進行抵消一次；
• 如果存在最終選票大于 0 的元素，我們還需要再次統計已選中元素的次數,檢查元素的次數是否大于 ?$\frac{n}{3}$?。

（3）對于 t = ?n / (m + 1)?，我們可以利用同樣的方法推斷出滿足這樣條件的元素最多只有 m 個。但是需要注意的是，此時算法時間復雜度為 O(n * m)，空間復雜度為 O(m)。

3.代碼實現

3.1.t = ?n / 2?

class Solution {public int majorityElement(int[] nums) {//設 candidate 為出現次數大于 ?n / 2? 的元素int candidate = 0;int cnt = 0;//遍歷數組 numsfor (int num : nums) {if (cnt == 0) {//重新確定選舉人candidate = num;}if (num == candidate) {//candidate 的票數加一cnt++;} else {//對拼消耗，即相當于 candidate 的票數減一cnt--;}}return candidate;}
}

① 上述算法的時間復雜度為 O(n)，空間復雜度為 O(1)。
② 有關 t = ?n / 2? 的摩爾投票算法的具體細節，可以參考本題官方題解。

3.2.t = ?n / 3?

class Solution {public List<Integer> majorityElement(int[] nums) {//滿足題目條件的元素最多只有兩個，我們設為 ele1 和 ele2int ele1 = 0;int ele2 = 0;//設 vote1 和 vote2 分別為 ele1 和 ele2 的贊成票數int vote1 = 0;int vote2 = 0;for (int num : nums) {if (vote1 > 0 && num == ele1) {//num 為第一個元素，則票數加 1vote1++;} else if (vote2 > 0 && num == ele2) {//num 為第二個元素，則票數加 1vote2++;} else if (vote1 == 0) {//選擇第一個元素ele1 = num;vote1++;} else if (vote2 == 0) {//選擇第二個元素ele2 = num;vote2++;} else {//三個元素 ele1、ele3、num 互不相同，則其票數減 1，即對拼消耗vote1--;vote2--;}}//cnt1 和 cnt2 分別記錄元素 ele1 和 ele2 出現的次數int cnt1 = 0;int cnt2 = 0;for (int num : nums) {if (vote1 > 0 && num == ele1) {cnt1++;}if (vote2 > 0 && num == ele2) {cnt2++;}}//檢查元素出現的次數是否滿足要求List<Integer> res = new ArrayList<>();if (vote1 > 0 && cnt1 > nums.length / 3) {res.add(ele1);} if (vote2 > 0 && cnt2 > nums.length / 3) {res.add(ele2);}return res;}
}

上述算法的時間復雜度為 O(n)，空間復雜度為 O(1)。

3.3.t = ?n / (m + 1)?

class Solution {public static List<Integer> majorityElements(int[] nums, int m) {//存儲多數元素的集合List<Integer> res = new ArrayList<>();//候選元素數組int[] candidates = new int[m];//對應候選元素的計數器數組int[] counts = new int[m];for (int num : nums) {//如果 num 存在于候選元素數組中，則將對應計數器加 1for (int i = 0; i < m; i++) {if (candidates[i] == num) {counts[i]++;break;}//如果 num 不在候選元素數組中且有空位置（計數器為 0），則將 num 加入候選元素數組if (candidates[i] == 0 && counts[i] == 0) {candidates[i] = num;counts[i]++;break;}}//如果候選元素數組已滿，則將所有計數器減 1if (counts[m - 1] != 0) {for (int i = 0; i < m; i++) {counts[i]--;}}}//驗證候選元素的計數器是否大于閾值for (int i = 0; i < m; i++) {int count = 0;for (int num : nums) {if (num == candidates[i]) {count++;}}if (count > nums.length / (m + 1)) {res.add(candidates[i]);}}return res;}
}

4.應用

大家可以去 LeetCode 上找相關的 Boyer-Moore 投票算法的題目來練習，或者也可以直接查看 LeetCode 算法刷題目錄 (Java) 這篇文章中的 Boyer-Moore 投票算法章節。如果大家發現文章中的錯誤之處，可在評論區中指出。