寻找水王

一.设计思路

由于要求实现这个程序的时间复杂度为O（n）所以无法进行排序算法。由于题目给出水王的发帖数为总帖数的一半以上，所以可以通过计算水王与其他人发帖数的差值（定义为n）来计算。假设水王的ID为第一个人的ID，从第二个人开始遍历，如果与水王的ID相同则n+1否则n-1，如果n<0则水王的ID变为当前遍历的ID。直至遍历结束。

二.代码

public class main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //用户id集合
        String a[]=new String[]{"a","a","ab","b","ab","a","abc","bc","a","a"};
        String b=a[0];
        int i=0,n=0;
        for(i=0;i<10;i++)
        {
            if(a[i]==b)
            {
                n=n+1;
            }
            else
            {
                n=n-1;
                if(n<0)
                {
                    b=a[i];
                    n=1;
                }
            }
        }
        System.out.print(b);
    }
}

 三.截图

四.总结

在上课的时候一直在想如何区分那个ID，没有灵活想到计算差值的方法，也是在听过高长志同学的讲解才稍微明白一点，然后就再顺着那个思路考虑。通过这种方法则可以控制在O（n）的时间复杂度之内。