一、題目：

三人行設計了一個灌水論壇。信息學院的學生都喜歡在上面交流灌水，傳說在論壇上有一個“水王”，他不但喜歡發帖，還會回復其他ID發的每個帖子。坊間風聞該“水王”發帖數目超過了帖子數目的一半。 如果你有一張當前論壇的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到這個傳說中的水王嗎？

二、設計思路：

????我們由題目可以知道這個水王的發表帖子的次數超過了所有帖子的一半， 所以采用兩兩相比的方式，若count=0，說明前面的數值相抵消，最后count>0,所以最后一次改變的ID就是水王的ID.

??? 1、定義一個count用來計數；

??? 2、先假設這個水王的ID是數組的第一個值，然后依次和后面的一個數比較，若兩數相等，count++；

??? 3、若兩數不相等，count——，若count<=0;說明與水王ID相等的比與水王ID不相等的次數要少或者是一樣，所以這個水王的ID就是不真正水王的ID?，將其后的一個值看作是水王的ID，將count清零，代表前面的數相抵消，繼續比較。

1 #include<iostream> 2 using namespace std; 3 void getwaterKing_ID(int Num_id,int Array_id[]) //用來獲取水王的ID 4 { 5 int waterking_id=Array_id[1]; //假設水王的ID為貼吧第一個發帖人的ID 6 int count=0; 7 for(int i=0;i<Num_id;i++) //利用ID不相等后兩兩相消，得出最后的count的值，由于水王的帖子是大于發帖子數組的一半的，最后count的值大于零 8 { 9 if(waterking_id==Array_id[i]) 10 { 11 count++; 12 } 13 if(waterking_id!=Array_id[i]) 14 { 15 count--; 16 } 17 if(count<=0) 18 { 19 waterking_id=Array_id[i]; 20 count=0; 21 } 22 23 } 24 25 cout<<waterking_id<<endl; 26 } 27 int main() 28 { 29 int array_id[100]; 30 int num_id; 31 cout<<"假設用數字來表示發表帖子的每個用戶的ID"<<endl; 32 cout<<"貼吧中發表的帖子數目為："<<endl; 33 cin>>num_id; 34 cout<<"假設發表帖子的ID :"<<endl; 35 for(int i=0;i<num_id;i++) 36 { 37 cin>>array_id[i]; 38 } 39 cout<<"這個貼吧中的水王的ID號為："<<endl; 40 getwaterKing_ID(num_id,array_id); 41 return 0; 42 }

四、測試用例
1、帖子數目是偶數：

2、帖子數目是奇數的：

五、實驗總結：雖然這次實驗是尋找水王的，但是抽象出來就是找一個數組中某個元素出現次數大于數組元素個數一半的那個數，按照我們以前的做法，我們都會是先遍歷一遍，然后排序，找出這個數值，但是這樣做算法不僅麻煩，而且時間復雜度很高，所以老師告訴了我們一種比較簡單的算法，就是抵消，最后剩下的書就是所要找的元素。通過這個試題，我不僅學會了一種簡單的算法，二是學會了一種思想，首先要學會轉化，把復雜的問題抽象為簡單的問題，然后就是尋找簡單的算法，這樣才能高效率的解決問題。

轉載于:https://www.cnblogs.com/luxin123/p/5510109.html

總結

以上是生活随笔為你收集整理的软件工程课堂作业——寻找“水王”的全部內容，希望文章能夠幫你解決所遇到的問題。

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