169. Majority Element

Majority Element

題目描述：給定一個大小為 n 的整數陣列，找出其中的「多數元素」——即出現次數嚴格超過 ⌊n/2⌋ 的元素。題目保證多數元素一定存在。

解題思路：本題最優解為 Boyer-Moore 投票演算法，可在 O(n) 時間、O(1) 空間內找到答案。

直覺理解：想像多數元素的士兵與其他元素的士兵互相廝殺，每次一個多數元素遇到一個非多數元素，就兩敗俱傷同歸於盡。由於多數元素數量超過一半，最後存活的一定是多數元素。

演算法步驟：

1. 維護一個候選者 candidate 與計數器 count（初始化為 0）。
2. 遍歷陣列中的每個元素：
   • 若 count == 0，將當前元素設為新的 candidate。
   • 若當前元素等於 candidate，count++。
   • 否則，count--（相互抵消）。
3. 遍歷結束後，candidate 即為多數元素。

由於題目保證多數元素存在，最終的 candidate 必然是答案，無需再次驗證。

時間複雜度：O(n) — 只需遍歷陣列一次，每個元素僅做常數次比較與加減法。

空間複雜度：O(1) — 只使用兩個額外變數 candidate 與 count，不隨輸入規模增長。

排序法 O(n log n)：將陣列排序後，位於索引 ⌊n/2⌋ 的元素必然是多數元素（因為它超過一半，排序後一定佔據中間位置）。實作極簡，但需要 O(n log n) 時間與 O(1) 或 O(log n) 空間（取決於排序算法）。

哈希表計數 O(n)：遍歷陣列並用哈希表統計每個元素的出現次數，一旦某元素次數超過 n/2 立即回傳。時間 O(n)，但空間 O(n)，不如 Boyer-Moore 的 O(1) 空間優化。

位元操作 O(32n)：逐 bit 投票——對 32 個 bit 位分別統計，若某 bit 上 1 的個數超過 n/2，則多數元素在該 bit 為 1。可用於不保證多數元素存在的情境作驗證。

1. 若多數元素不保證存在，Boyer-Moore 演算法仍然有效嗎？需要如何修改才能正確處理這種情況？
2. 若題目改為找出所有出現次數超過 ⌊n/3⌋ 的元素（LeetCode 229），Boyer-Moore 的思路要如何延伸？
3. 在分散式系統中，若資料分布在多台機器上，你會如何設計一個高效的多數元素查找方案？