课堂练习-水帖之王（水王）

　　今天的课堂练习是关于众数的查找。但是在这个枯燥的算法上，老师提出了一个很有意思而且很贴近我们日常上网生活的情景：有一个网友，他在一个吧里发帖数最多，而且占到了一半以上，

现在给出所有的帖子以及帖主的姓名，现在要求找出这个水帖霸王。

　　我们观察题目，其实第一想到的就是用二重循环把每个id对应出现的次数全部都算出来，再进行一次比较，求出次数最大值对应的帖主就是水王。但是，这毕竟不是最优的方法，在老师提出复

杂度为n的时候，我瞬间就懵了。以前求众数不都是二重循环嘛，一个循环体难道就能实现？

　　在我苦思不得其解的时候，老师给出了一个提示：帖数占到了一半以上。在这之前，我明白帖数占到一半以上就一定是发帖最多的用户一定没问题，以为这是两个表达相同意思的条件，但细细

想却不是这样。我用的二重循环只是利用了发帖最多这个条件，然而发帖数一半呢？

　　最后的得出了解题思路，一次循环两两进行比较，如果相同，则暂且把它定为水王，如果不同，则将这俩剔除。这样比较到最后，剩下的那个未抵消的用户就一定是水王本王。

　　代码如下：

 1 package tieba;
 2 
 3 import java.util.Scanner;
 4 
 5 class tie
 6 {
 7     private int num;
 8     private String id;
 9     public tie() {};
10     public tie(int num,String id)
11     {
12         this.num=num;
13         this.id=id;
14     }
15     public int getNum() {
16         return num;
17     }
18     public void setNum(int num) {
19         this.num = num;
20     }
21     public String getId() {
22         return id;
23     }
24     public void setId(String id) {
25         this.id = id;
26     }
27     
28 }
29 public class tiezi {
30 
31     public static void main(String[] args) {
32         // TODO 自动生成的方法存根
33            Scanner sc =new Scanner(System.in);
34              
35             System.out.println("请输入ID的个数：");
36             int a=sc.nextInt();
37             int b[]=new int[a];
38             System.out.println("请输入ID");
39             for(int i=0;i<a;i++)
40             {
41                 b[i]=sc.nextInt();
42             }
43              
44             int water=b[0];
45             int k=1;
46             for(int i=1;i<a;i++)
47             {
48                 if(water!=b[i])
49                 {
50                     k=k-1;
51                     if(k<=0)
52                     {
53                         water=b[i+1];
54                         k=1;
55                         i++;
56                     }
57                 }
58                 else
59                 {
60                     water=b[i];
61                     k=k+1;
62                 }
63             }
64              
65             System.out.println("水王为"+water);
66 
67         
68     }
69     
70     
71     
72     }

课堂练习-水帖之王（水王）

相关推荐