標簽：LeetCode 169, 摩爾投票法, 多數元素, 算法擴展, 數組處理

在解決多數元素問題時，我們學習了經典的摩爾投票法處理出現次數超過 n/2 的情況。那么，當問題擴展為找出出現次數超過 n/3 的元素時，該如何解決呢？本文將深入探討摩爾投票法的擴展應用。

問題描述

給定一個大小為 n 的整數數組，找出所有出現次數 大于 ?n/3? 的元素。要求時間復雜度 O(n)，空間復雜度 O(1)。

示例：

輸入：[1,1,1,3,3,2,2,2]
輸出：[1,2]
解釋：1 和 2 都出現 3 次，大于 ?8/3? = 2

關鍵洞察

1. 數學約束：出現次數超過 n/3 的元素最多有 2 個

   • 如果 3 個元素都超過 n/3，總次數將超過 n，不可能

2. 擴展思路：使用兩個候選元素和兩個計數器

   • 維護兩個候選元素 candidate1, candidate2
   • 維護對應的計數器 count1, count2
   • 使用抵消策略處理其他元素

算法原理

1. 初始化：兩個候選元素設為特殊值（如 null），計數器設為 0
2. 投票階段：
   • 當前元素等于任一候選元素 → 對應計數器加 1
   • 當任一計數器為 0 → 將當前元素設為新候選
   • 當前元素不等于任一候選 → 兩個計數器都減 1（抵消）
3. 驗證階段：檢查候選元素是否真正超過 n/3

Java 實現

import java.util.*;class Solution {public List<Integer> majorityElement(int[] nums) {// 初始化候選元素和計數器Integer candidate1 = null;Integer candidate2 = null;int count1 = 0;int count2 = 0;// 第一輪遍歷：投票過程for (int num : nums) {if (candidate1 != null && num == candidate1) {count1++;} else if (candidate2 != null && num == candidate2) {count2++;} else if (count1 == 0) {candidate1 = num;count1 = 1;} else if (count2 == 0) {candidate2 = num;count2 = 1;} else {// 抵消操作count1--;count2--;}}// 第二輪遍歷：驗證候選元素List<Integer> result = new ArrayList<>();count1 = 0;count2 = 0;for (int num : nums) {if (candidate1 != null && num == candidate1) count1++;if (candidate2 != null && num == candidate2) count2++;}int n = nums.length;if (count1 > n/3) result.add(candidate1);if (count2 > n/3) result.add(candidate2);return result;}
}

算法演示

以數組 [1,2,3,2,1,2,3,1,2] 為例（n=9，需要出現次數 > 3）

投票階段

元素	candidate1	count1	candidate2	count2	操作說明
1	1	1	null	0	初始化 candidate1
2	1	1	2	1	初始化 candidate2
3	1	0	2	0	抵消 (1-1, 2-1)
2	1	0	2	1	count1=0, 使用candidate2
1	1	1	2	1	重置 candidate1
2	1	1	2	2	增加 candidate2
3	1	0	2	1	抵消
1	1	1	2	1	重置 candidate1
2	1	1	2	2	增加 candidate2

驗證階段

• candidate1 = 1 → 出現次數：4 > 3
• candidate2 = 2 → 出現次數：4 > 3
• 結果：[1, 2]

復雜度分析

• 時間復雜度：O(2n) = O(n)，兩次線性遍歷
• 空間復雜度：O(1)，僅使用常數空間（兩個候選元素和兩個計數器）

算法關鍵點

1. 候選元素初始化：使用包裝類型 Integer 以便處理 null 值
2. 條件判斷順序：優先檢查是否匹配候選元素，再檢查計數器是否為0
3. 抵消策略：當元素與兩個候選元素都不同時，同時減少兩個計數器
4. 驗證必要性：投票結果需要驗證，因為：
   • 計數器可能被其他元素干擾
   • 數組可能沒有滿足條件的元素

通用化公式

摩爾投票法可進一步擴展為尋找出現次數超過 n/k 的元素：

1. 最多有 k-1 個候選元素
2. 維護 k-1 個候選元素和計數器
3. 投票階段：
   • 匹配候選 → 對應計數器加1
   • 計數器為0 → 設為新候選
   • 都不匹配 → 所有計數器減1
4. 驗證候選元素的實際出現次數

實際應用場景

1. 大數據分析：從海量數據中找出高頻項
2. 網絡流量監控：檢測異常高頻訪問
3. 推薦系統：識別熱門內容
4. 日志分析：查找頻繁出現的錯誤類型
5. 選舉系統：統計多候選人得票情況

邊界情況處理

1. 候選元素為 null 的情況：

   if (candidate1 != null && num == candidate1)
   

2. 數組長度小于3：

   • 當 n < 3 時，?n/3? = 0，所有元素都滿足條件
   • 但實際需統計出現次數 > 0 的元素（根據定義）

3. 沒有滿足條件的元素：

   // 驗證階段會過濾掉不滿足條件的候選
   if (count1 > n/3) result.add(candidate1);
   

總結

擴展摩爾投票法展示了算法設計的精妙之處：

1. 數學洞察：利用問題約束（最多 k-1 個候選）
2. 空間優化：O(1) 空間解決統計問題
3. 高效性：O(n) 時間復雜度
4. 通用性：可擴展為 n/k 問題

掌握這種擴展思維，能幫助我們在面對各類統計問題時，設計出高效的空間優化算法。摩爾投票法不僅是解決多數元素問題的利器，更是算法設計中"以空間換時間"思想的經典體現。

思考挑戰：如何擴展該算法處理出現次數超過 n/4 的情況？歡迎在評論區分享你的解決方案！