给定一个数组，其中有一个元素的出现次数超过1/2，如何快速的找出这个元素。这个问题在《编程之美》中是这样描述的：
“研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？”
两个问题殊途同归，，都是快速查找数组中出现次数超过一半的元素。
最直接的解法：对数组进行排序，取n/2 + 1个元素即为所求，这种算法的复杂度最坏的情况下是O(n^2),平均情况下是O(n*log2n)。
另一种方式：可以根据不同就抵消，相同就增一的计算器完成。设置一个当前值和当前值的计数器，初始化当前值为数组首元素，计数器值为1，然后从第二个元素开始遍历整个数组，对于每个被遍历到的值a[i]
1 如果a[i]==currentValue，则计数器值加1
2 如果a[i] != currentValue， 则计数器值减1，如果计数器值小于0，则更新当前值为a[i]，并将计数器值重置为1
#include <stdio.h>#include <stdlib.h>int FindMoreValue(int arr[], int n){int i;int curr_count = 1;int curr_value = arr[0];for(i = 1; i < n; i++){if(arr[i] == curr_value){curr_count++;}else{curr_count–;if(curr_count < 0){curr_value = arr[i];curr_count = 1;}}}if(curr_count > 0){return curr_value;}else{//不存在出现次数超过一半的元素return -1;}}int main(int argc, char * argv[]){int arr[10] = {1,1,1,1,1,1,2,3,4,5};int value = FindMoreValue(arr, 10);printf("Find Value:%d\n", value);}如果要查找数组中出现次数超过1/3的两个元素呢？#define NAN (0.0 / 0.0)int FindMore(int arr[], int n, int cans[2]){int i;if(n < 2){return -1;}int times[2];times[0] = times[1] = 0;cans[0] = cans[1] = NAN;for(i = 0; i < n; i++){if(arr[i] == cans[0]){times[0]++;}else if(arr[i] == cans[1]){times[1]++;}else{times[0]–;times[1]–;if(times[0] < 0){cans[0] = arr[i];times[0] = 1;}else if(times[1] < 0){cans[1] = arr[i];times[1] = 1;}}}return 0;}以此类推，求出现次数超过1/4的三个元素等等。
告诉自己，我这次失败了，重新开始吧!下次我会吸取教训，不让自己犯同样的错误的
