学习难点记录

学习python过程中遇到难点时，想不明白先记录下来，过后再回过头看看说不定豁然开朗~~

1.

如果有一个列表，其中占比超过一半的元素称之为主要元素，那么如何获取一个列表的主要元素呢？

题目给定的列表是：[2, 2, 4, 2, 3, 6, 2]

解题思路：

根据主要元素的定义，对列表进行排序操作之后，主要元素必然会出现在列表长度一半之后的一个位置上。

所以，我们只需要判断列表中是否有超过一半的元素与中间元素相同即可（如果有，中间元素为主要元素；否则，不存在主要元素。

？其实上面这道题有一个经典的解法，就是使用摩尔投票法（boyer–moore majority vote）。

摩尔投票法有时候也被称为“多数投票法”，该算法解决的问题是如何在任意多的候选人中（选票无序），找到获得票数最多的那个。

摩尔投票法分为两个阶段：

对抗阶段：分属两个候选人的票数进行两两对抗抵消

计数阶段：计算对抗结果中最后留下的候选人票数是否有效

大家不妨可以将摩尔投票法的工作原理想象为诸侯争霸，假设每个国家都是全民皆兵，并且打起仗来都是以 1 换 1 的形式消耗人口，当一个国家人口总数为 0，那么 gameover，ok，如果某国人口数量超过所有国家总人口的一半，最终赢家就肯定是它。

？利用“摩尔投票法”来找出占比数量最多的两个元素  第022讲