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

分析與解法：

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

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

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