This world may be rough around the edges, but it’s got its charms.

这个世界可能很粗野，但有其魅力所在。

问题描述

来源：LeetCode面试题 17.10

难度：简单

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回-1。请设计时间复杂度为O(N)、空间复杂度为O(1)的解决方案。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]

输出：5

示例 2：


输入：[3,2]

输出：-1

示例 3：


输入：[2,2,1,1,1,2,2]

输出：2

摩尔投票算法解决

这题是让求主要元素，主要元素就是在数组中占比超过一半的元素。咋一看这题很简单，我们可以通过排序或者使用HashMap都是可以解决的。但这题要求时间复杂度为O(N)，空间复杂度为O(1)，很明显上面两种方式都不符合要求。

除了上面两种方式我们可以使用摩尔投票算法来解，维基百科对摩尔投票算法是这样解释的。

摩尔投票算法是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。


上面说了一大堆，主要说了两层意思：

第一就是找出主要元素（不一定有）
第二判断这个数是否是主要元素。

摩尔投票算法的原理就是使用两个变量，一个major记录当前数字，一个count记录当前数字出现的次数，遇到相同的count就加1，遇到不同的就减1，当count小于0的时候，说明前面的都相互抵消完了，major和count都要重新赋值……，最后再判断major是否是主要元素即可。我们来举个例子


假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是不同国家每两个人都同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜（假设主要元素存在）。

就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个主要元素，（这里有个前提，就是主要元素必须存在），来看下代码

时间复杂度：O(N)，两个for循环，不是嵌套的。
空间复杂度：O(1)，使用了两个变量。


本文原创，未经作者允许不可转载！
更多内容，欢迎关注作者微信公众号：数据结构和算法！