问题：在长度为n的数组中找出重复次数超过n/2的数（假设一定存在）。
存在O(n)的时间复杂度和O(1)的空间复杂度的解法，即摩尔投票法
前言： 直接看摩尔投票法的代码，很难理解其算法思想，过一段时间就会忘记代码怎么写的，在此之前其实我就已经看过不下两次代码了，只记得有这样一种方法，但是具体的就不记得了，所以我们要理解其原理。
摩尔投票法
摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。
那么如何在O(n)的时间复杂度，只遍历一次数组就把不同的数都删除呢？摩尔投票法的代码实现是具有技巧性的，并不是真的要删除数组里的数，只是把遍历过程当作一个删除过程。
使用一个虚拟数组存放还未和不同数字一起删除的数，这个数组只能有若干个同一数字，不可能存在不同的数，因为如果存在不同的数就会被删去，而不会放到此数组中。
当数组遍历到当前元素时，若虚拟数组为空，就将当前元素加进去；若虚拟数组非空，就比较当前元素是否和虚拟数组中的元素相同，如果不同就删去虚拟数组中的一个元素，同时当作当前元素也被删除，接着遍历下一元素，这样就相当于一对不同的数字被删除，如果相同，就把当前元素加到虚拟数组中。最终遍历完数组，虚拟数组中的元素就是要找的元素。
由于虚拟数组中只会存在若干个相同元素，那么可以仅用两个变量表示这个虚拟数组，一个变量存值，另一个变量存放个数。
更详细的描述可以参考知乎上喝七喜的回答
c语言代码如下：
#include<stdio.h>
#define LEN 10
int main(){
int a[] = {2,2,1,1,1,3,3,1,1,1};
int x, cx = 0;//表示一个虚拟数组
for(int i = 0; i < LEN; ++i){
if(cx == 0) x = a[i], cx = 1;//虚拟数组为空，加入当前元素
else if(x == a[i]) ++cx;//数组非空，当前元素与虚拟数组元素相同，加入当前元素
else --cx;//数组非空，当前元素与虚拟数组元素不同，删除一对不相同的元素
}
printf("超过1/2的数是：%d",x);
return 0;
}
类似的问题： 在长度为n的数组中找出重复次数超过n/3的数（不一定存在）。
容易知道，重复次数超过数组长度1/3的数最多有两个。用反证法容易证得。
同样的思路，使用两个虚拟数组，每次删除三个不同的数，最终虚拟数组中的两个数就是可能的答案，此时再遍历一遍数组，做一个验证即可。
c语言代码如下：
#include<stdio.h>
#define LEN 8
int main(){
int a[] = {1,2,1,2,3,3,1,2};
int x, y, cx = 0, cy = 0;//两个虚拟数组
for(int i = 0; i < LEN; ++i){
if(x == a[i]) ++cx;
else if(y == a[i]) ++cy;
else if(cx == 0) x = a[i], cx = 1;
else if(cy == 0) y = a[i], cy = 1;//这两个判断不能提前，因为可能把x,y赋为同一个值
else --cx, --cy;
}
cx = 0,cy = 0;
for(int i = 0; i < LEN; ++i){//锁定候选目标，遍历数组，计数，做验证
if(a[i] == x) ++cx;
else if(a[i] == y) ++cy;
}
if(cx > LEN/3){
printf("超过1/3的数有：%d\n",x);
}
if(cy > LEN/3){
printf("超过1/3的数有：%d\n",y);
}
return 0;
}
