摩尔投票算法

摩尔投票算法的时间和空间都很低，时间复杂度为 ，空间复杂度为 ，这也是选择遮盖算法的原因。

算法原理：每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。

• 算法在局部变量中定义一个序列元素 m 和一个计数器 i，初始化的情况下计数器为 0；
• 算法依次扫描序列中的元素，当处理元素 x 的时候，如果计数器为 0，那么将 x 赋值给 m，然后将计数器(i)设置为 1；
• 如果计数器不为 0，那么将序列元素 m 和 x 比较，如果相等，那么计数器加 1，如果不等，那么计数器减 1。
• 处理之后，最后存储的序列元素 m，就是这个序列中最多的元素。（如果不确定是否存储的元素 m 是最多的元素，还可以进行第二遍扫描判断是否为最多的元素）