一個論壇中又一大“水王”，他不但喜歡發(fā)帖，還會回復其他ID發(fā)的每個帖子。該“水王”發(fā)帖數(shù)目超過了總數(shù)的一半。如果你又一個當前論壇所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出這個傳說中的水王嗎？

分析與解法：

　　首先想到的是一個最直接的方法，我們可以隊所有ID進行排序。然后再掃描一遍排好序的ID列表，統(tǒng)計各個ID出現(xiàn)的次數(shù)。如果某個ID出現(xiàn)的次數(shù)超過總數(shù)的一半，那么就輸出這個ID。這個算法的時間復雜度為O(N*log2N+N)。

如果一個ID出現(xiàn)的次數(shù)超過總數(shù)N的一半。那么，無論水王的ID是什么，這個有序的ID列表中的第N/2項（從0開始編號）一定會是這個ID（讀者可以試著證明一下）。省去重新掃描一遍列表，可以節(jié)省一點算法耗費的時間。如果能夠迅速定位到列表的某一項（比如使用數(shù)組來存儲列表），除去排序的時間復雜度，后處理需要的時間為O（1）。

如果每次刪除兩個不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出現(xiàn)的次數(shù)仍然超過總數(shù)的一半。看到這一點之后，就可以通過不斷重復這個過程，把ID列表中的ID總數(shù)降低（轉化為更小的問題），從而得到問題的答案。新的思路，避免了排序這個耗時的步驟，總的時間復雜度只有O（N），且只需要常數(shù)的額外內存。