课堂作业-找水王

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，

传说在论坛上有一个“水王”，他不但喜欢发帖，

还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，

你能快速的找到这个传说中的水王吗？

 

设计思想：原打算对发帖人和相对应的回帖人进行排序，后来有同学提到用两两相消法实现，于是两两对比，相同就留下不同则消去，剩下最多的就是水王。

 

程序源代码：

import java.util.*;
public class Findwaterking {
    public static  void main(String args[]){
        Scanner sc =new Scanner(System.in);
         
        System.out.println("请输入ID个数：");
        int a=sc.nextInt();
        int b[]=new int[a];
        System.out.println("请输入ID：");
        for(int i=0;i<a;i++)
        {
            b[i]=sc.nextInt();
        }
         
        int waterking=b[0];
        int k=1;
        for(int i=1;i<a;i++)
        {
            if(waterking!=b[i])
            {
                k=k-1;
                if(k<=0)
                {
                    waterking=b[i+1];
                    k=1;
                    i++;
                }
            }
            else
            {
                waterking=b[i];
                k=k+1;
            }
        }
         
        System.out.println("水王为"+waterking);
    }
}

结果截图：

　　

实验总结：

　　程序仍有Bug，如果为1 2 1 3 1 4 1 5 1 6...等这种水王ID刚好与其余人ID间隔开，就无法找出水王。(此处有问题...因为题设水王发帖过半数，所以水王ID出现次数一定超过总ID出现次数的一半[此句修改于2016/5/27])