學習難點記錄

學習python過程中遇到難點時，想不明白先記錄下來，過後再回過頭看看說不定豁然開朗~~

1.

如果有一個清單，其中占比超過一半的元素稱之為主要元素，那麼如何擷取一個清單的主要元素呢？

題目給定的清單是：[2, 2, 4, 2, 3, 6, 2]

解題思路：

根據主要元素的定義，對清單進行排序操作之後，主要元素必然會出現在清單長度一半之後的一個位置上。

是以，我們隻需要判斷清單中是否有超過一半的元素與中間元素相同即可（如果有，中間元素為主要元素；否則，不存在主要元素。

？其實上面這道題有一個經典的解法，就是使用摩爾投票法（boyer–moore majority vote）。

摩爾投票法有時候也被稱為“多數投票法”，該算法解決的問題是如何在任意多的候選人中（選票無序），找到獲得票數最多的那個。

摩爾投票法分為兩個階段：

對抗階段：分屬兩個候選人的票數進行兩兩對抗抵消

計數階段：計算對抗結果中最後留下的候選人票數是否有效

大家不妨可以将摩爾投票法的工作原理想象為諸侯争霸，假設每個國家都是全民皆兵，并且打起仗來都是以 1 換 1 的形式消耗人口，當一個國家人口總數為 0，那麼 gameover，ok，如果某國人口數量超過所有國家總人口的一半，最終赢家就肯定是它。

？利用“摩爾投票法”來找出占比數量最多的兩個元素  第022講