2.3 寻找发帖水王

1 题目

Tango是微软亚洲研究 院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每 个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找 出这个传说中的Tango水王吗？

2 分析

题目的实质是从一个数组中找到出现次数大于数组长度一半的元素。即[1,2,3,1,1,1]数组，如何找到1

3 解法

书中列举了几种解法。
1）先排序，在统计各ID出现的次数，超过总数一半的即为所求的。时间复杂度为O(nlogn+n)。
2）先排序，排序好后数组中n/2位置处的即为所需元素(前提是一定存在)，比如上面的排好序后为[1,1,1,1,2,3],7/2位置处的为1。时间复杂度为O(n*logn)
3)假如注意到一个事实，假定a为数组中超过一半的元素，那么数组中除去两个不相同的元素，a依然是超过现在数组元素一半的元素。这个可以使用简单的数学证明下。

4 代码

我们使用一个candidate表示候选元素，使用一个nTimes表示候选元素的当前出现次数，遍历数组，会有以下几种情况：

1. nTimes == 0 表示可能是遍历的第一个元素，也可能是消除了若干对不同元素后的结果，但对应的处理很简单，就是将当前的元素作为候选元素，同时nTimes 置为1
   2)nTimes != 0 分为两种情况:一种是候选元素和当前遍历元素相等，则说明遇到的是相同的元素，不能删除，需要nTimes自增1;另一种是不相同，则表示找到了两个不同的元素，将nTimes自减1。

        int[] a = {1,1,1,2,2,2,2,3,1,1,1};
        int candidate = 0;
        int nTimes = 0;
        for(int i=0; i< a.length; i++){
            if(nTimes == 0){
                candidate = a[i];
                nTimes = 1;
            }else{
                if(candidate == a[i]){
                    nTimes++;
                }else{
                    nTimes--;
                }
            }
        }
        System.err.println(candidate);

5 扩展

随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？
使用c1,c2,c3代表候选元素，使用t1,t2,t3表示对应的候选元素的当前出现次数，遍历数组，当前遍历元素为k,会有以下几种情况:

1. k 不在c1 c2 c3 里面，而且t1 t2 t3 有为0的，那么就说明候选元素还没有选完，需要将对应t为0的c置为k,同时对应的t置为1
   2)k 不在c1 c2 c3 里面，且t1 t2 t3 均不为0，说明遇到了四个不同的元素，t1 t2 t3 均自减1
   3)k 在c1 c2 c3 里面，则对应的t自增1
   前提是数组中的元素不会为-1

public static void main(String[] args){
        int[] b = {1,2,3,4,1,2,3,4,1,2,3,4,3,2,1};
        int[] c = {-1,-1,-1};
        int[] t = {0,0,0};
        for(int i = 0; i < b.length; i++){
            int whichCandidate = getCandidate(b[i], c);
            int which = getFreeStore(t);
            if(whichCandidate == -1 && which != -1){
                c[which] = b[i];
                t[which] = 1;
            }else if(whichCandidate == -1 && which == -1){
                t[0]--;
                t[1]--;
                t[2]--;
            }else if(whichCandidate != -1){
                t[whichCandidate]++;
            }
        }
        System.err.println(c[0]+" " + c[1] +" " + c[2]);
    }
    public static int getCandidate(int c,int[] candidate){
        for(int i = 0; i < candidate.length; i++){
            if(c == candidate[i]){
                return i;
            }
        }
        return -1;
    }
    public static int getFreeStore(int[] t){
        for(int i = 0; i < t.length;i++){
            if(t[i] == 0){
                return i;
            }
        }
        return -1;
    }