找水王 - 天天看點

一、題目與要求

題目、三人行設計了一個灌水論壇。資訊學院的學生都喜歡在上面交流灌水，傳說在論壇上有一個“水王”，他不但喜歡發帖，還會回複其他ID發的每個文章。坊間風聞該“水王”發帖數目超過了文章數目的一半。

要求、如果你有一張目前論壇的文章（包括回帖）清單，其中文章的作者的ID也在其中，你能快速的找到這個傳說中的水王嗎？

二、設計思路

　　首先看到這道題，最基礎的解法就是統計每個id發帖的數量，最後比較大小，這樣就可以找到“水王”，不過，無疑這種方法是最麻煩的，時間複雜度為O(n^2);
那麼，要降低複雜度，就要考慮到這個題目的條件，“水王”發帖超過了文章數目的一半，那麼如果對所發文章的ID進行排序，那麼居中的ID必然是水王，這樣便誕生了第二種解法，不過時間複雜度為O(n*log^n);仍然不是很理想
　　為了使時間複雜度為O(n),我們可以對所有的ID進行計數，從第一個開始，計數為single=0，标記為ID0;向後周遊，如果ID1與ID0相同，那麼singl+1(相當于對相同ID計數一次)，否則single—1（相當于不再考慮該ID,直接删除）,r如果single=0的話，标記為ID(x);最後結果即為ID(x);

三、源代碼

```
// waterking.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include"iostream"
using namespace std;

void Data(int length,int A[])
{
    cout<<"請輸入ID清單："<<endl;
    for(int i=0;i<length;i++)
    {
        cin>>A[i];
    }
}

int main()
{
    int length;
    int single=0;
    int ID;        //設定信号量
    cout<<"請輸入文章數量：";
    cin>>length;
    int * waterking=new int [length];
    Data(length,waterking);
    for(int i=0;i<length;i++)
    {
        if(single==0)
        {
            ID=waterking[i];
            single++;
        }
        else if(waterking[i]==ID)
        {
            single++;
        }
        else
        {
            single--;
        }
    }
    cout<<"水王為："<<ID<<endl;
    return 0;
}      
```
四、實驗結果

找水王

找水王

五、結果分析

　　這是很典型的要求算法優化，代碼也不長，主要是考慮應該用什麼樣的方法實作，要怎樣去實作代碼的優化。要實作代碼的優化，首先要解決的是找到問題解決的核心，從核心入手，才能有思路去探讨解決問題的途徑。這道題中，根據條件我們可以知道，半數以上文章都是一個ID的，是以，隻要找到中間的值，就能找到所謂的水王，但是，這樣的優化還不夠完美，要将他的時間複雜度降為O(n^2),就要考慮相同ID和不同ID之間的關系，對于不同的ID，直接摒除，那麼就可以排除水王的存在，因為水王發帖數足夠大，那麼最後剩下的肯定是水王。

　　這個題中，代碼的優化過程不是一蹴而就的，而是逐漸的思考深入，找到問題的關鍵點才漸漸實作理想的優化過程。而這個過程，恰恰是我們需要關注的。