Java实验--关于课上找“水王”问题分析

问题的表述就是说有那么一个人，他在一个论坛上发帖，然后每贴必回，自己也发帖。那么这个人在发帖的数目上就超过了整个论坛的帖子数目的一半以上。

我对这个问题一开始的思路是，用SQL语句获取整个列表中的数据，每次用sql读取id出现次数List储存这个人的id，接着读取下一个id，若在list中存在则跳过。若发帖数大于数据/2则这个人是“水王”。

我在课上完成的代码如下，其中list是我定义的获取全部数据的一个sql函数：

ClassService service=new ClassService();

        String []strList=new String[]{"no","id"};

        @SuppressWarnings("unchecked")

        List<People> people= (List<People>) service.list("reply",strList,new People().getClass());

        List<String> ids=new ArrayList<String>();

        int num=people.size();

        int count=0;

        for(int i=0;i<=num/2;i++)

        {

            String itId=people.get(i).getId();

            if(ids.contains(itId))

                continue;

            String []strList1=new String[]{"id","no"};

            String []strList2=new String[]{itId};

            @SuppressWarnings("unchecked")

            List<People> peopleTemp= (List<People>) service.search("reply",strList1,strList2,new People().getClass());

            if(peopleTemp.size()>=people.size()/2)

            {

                System.out.println("水王是"+itId);

                System.out.println("他的发帖数是"+peopleTemp.size());

                break;

            }

            ids.add(itId);

}

要求二是对上述算法将复杂度降低到O(n)，我在上课的期间并没有想到好的思路，原因在于：

要求1.不能定义变量，只要求一次循环便得出最后水王是谁。

我尝试利用list.add(list.remove())嵌套，可惜最终实验没有成功，也许是过于愚昧，并不能想出对应的解决思路。

同学的思路：定义两个变量(我感觉已经不符合题意了)，然后在这个的基础上进行一次循环得出水王的值。