找水王

一、題目：

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

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

二、設計思想：

水王的文章超過一半，在一次周遊的時候進行計數，初始值n=0；從第一個開始用m記錄下ID，如果相鄰兩個ID一樣，n就加一，m不變，如果不一樣，n就減一，m不變，直到當n小于0的時候，讓m為第二個ID,n=0。最後n>0，m表示的ID就是水王。

三、源代碼：

public class main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //ID号
        int ID[]={2012,1234,1011,2012,1011,2012,2012,1011,2012,2012,2341,2012,2012,2012,1023,1230,2012};
        int n=0;
        int m=0;
        m=ID[0];
        for(int i=0;i<9;i++)
        {
            if(m==ID[i+1])
            {
                n++;
            }
            else
            {
                n--;
                if(n<0)
                {
                    m=ID[i+1];
                    n=0;
                }
            }
        }
        System.out.print("水王的ID是:"+m);
    }

}      

四、程式運作截圖：

五、個人總結：

      剛接觸到題目，最先想到的是對ID進行一個一個的周遊，記錄下每個ID出現的次數，但是這種方法太麻煩，時間複雜度很大。後來老師提到了消滅星星的方法，但是消滅星星是需要消滅相同的星星，在這裡消滅一樣的不可行，隻有消滅不一樣的，在同學的提醒下想到了這種方法。