概念
提问
给定一个int型数组，找出该数组中 出现次数最多的int值。
解决方案
遍历该数组，统计每个int值出现次数，再遍历该集合，取出出现次数最大的int值。
这算是一个比较经典的解决办法，其中可能会用到Map来做统计。如果不使用Map，则时间复杂度会超过线性复杂度。除此之外，也没有什么特别好的办法。
今天在leetcode上遇到这样一道题目，
提问
给定一个int型数组，找出该数组中出现次数大于数组长度一半的int值。
解决方案
遍历该数组，统计每个int值出现次数，再遍历该集合，找出出现次数大于数组长度一半的int值。
同样的，该解决办法也要求使用Map，否则无法达到线性的时间复杂度。
那么对于这个问题，有没有什么不使用Map的线性算法呢？
答案就是今天我们要提到的 摩尔投票法。利用该算法来解决这个问题，我们可以达到线性的时间复杂度以及常量级的空间复杂度。
首先我们 注意到这样一个现象： 在任何数组中，出现次数大于该数组 长度一半的值只能有一个。
通过数学知识，我们可以证明它的正确性，但是这并不在我们这篇博客里涉及。
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。
那么有没有可能出现最后有两种或两种以上元素呢？根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。因此，最终只能是剩下零个或一个元素。
在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数 $f(c)$，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。
程序开始之前，元素c为空，$f(c)=0$。遍历数组A：
- 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
- 如果当前元素
A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来) - 如果当前元素
A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来) - 如果当前元素
A[i] != c，那么 $f(c) -= 1$ (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])
如果遍历结束之后，f(c)不为0，则找到可能元素。
再次遍历一遍数组，记录c真正出现的次数，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。
看java代码示例，为了保证每一步骤的清晰性，代码没有经过优化。
/**
* 算法基础：摩尔投票法
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
int majority = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
majority = num;
count++;
} else {
if (majority == num) {
count++;
} else {
count--;
}
}
}
int counter = 0;
if (count <= 0) {
return -1;
} else {
for (int num : nums) {
if (num == majority) counter ++;
}
}
if (counter > nums.length / 2) {
return majority;
}
return -1;
}
其实这样的算法也可以衍生到其它频率的问题上，比如说，找出所有出现次数大于n/3的元素。同样可以以线性时间复杂度以及常量空间复杂度来实现。
常见解题思路
- 摩尔投票法。该算法用于1/2情况，它说：“在任何数组中，出现次数大于该数组长度一半的值只能有一个。”
- 数组中第一位数作为默认的候选人(cand_num)
- 依次向后遍历
- 当出现相同的数(cand_num) 则 投票数 count +1
- 当出现不同的数 则投票(count_num) 投票数 count -1
- 当 count ==0 ，则跟换候选人，并 count 重制为 1
- 遍历完后 count_num 则为最终答案
- 类似题目有