首页 > 代码库 > 课堂练习-找水王

课堂练习-找水王

题目:

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水,传说在论坛上有一个“水王”,他不但喜欢发帖,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。 如果你有一张当前论坛的帖子(包括回帖)列表,其中帖子的作者的ID也在其中,你能快速的找到这个传说中的水王吗?

 

设计思想:

删除两个不同的ID(不管是否包含水王的ID),那么,在剩下的ID列表中,水王ID出现的次数仍然超过总数的一半。可以通过不断重复这个过程,把ID列表中的ID总数降低,从而得到水王ID

package shuiwang;

import java.util.Scanner;

public class shuiwang {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		        Scanner sca=new Scanner(System.in);
		        System.out.println("请输入帖子总数:");
		          int count=sca.nextInt();
		         int a[]=new int[count];
		         
		         int i,j=1,sw;
		        System.out.println("请分别输入帖子ID:");
		        for(i=0;i<count;i++)
		        {
		            a[i]=sca.nextInt();
		        }
		        sw=a[0];
		        for(i=1;i<count;i++)
		        {
		           if(sw!=a[i])
		           {
		                j=j-1;
		                if(j<=0)    
		                {
	                    sw=a[i+1];    
		                   j=1;     
		                    i++;
		                }
		           }
		           else
		           {
		                sw=a[i];
		                j=j+1;
		            }
		        }
		        System.out.println("水王ID是 "+sw);
	   }
	}

 实现截图:

技术分享

技术分享

 

个人总结:

在学习过程中我们要学会换一种思路去思考问题,突破常规的想法,可以找到更加高效的算法。

课堂练习-找水王