今天的課堂練習是關于眾數的查找。但是在這個枯燥的算法上，老師提出了一個很有意思而且很貼近我們日常上網生活的情景：有一個網友，他在一個吧里發帖數最多，而且占到了一半以上，

現在給出所有的帖子以及帖主的姓名，現在要求找出這個水帖霸王。

　　我們觀察題目，其實第一想到的就是用二重循環把每個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 }

?

轉載于:https://www.cnblogs.com/Aduorisk/p/10971541.html

總結

以上是生活随笔為你收集整理的课堂练习-水帖之王（水王）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。