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

分析與解法：

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

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

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