学步园

   给定一个数组，其中有一个元素的出现次数超过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的三个元素等等。