Tango是微軟亞洲研究院的一個(gè)試驗(yàn)項(xiàng)目。研究院的員工和實(shí)習(xí)生們都很喜歡在Tango上面交流灌水。傳說，Tango有一大“水王”，他不但喜歡發(fā)貼，還會(huì)回復(fù)其他ID發(fā)的每個(gè)帖子。坊間風(fēng)聞該“水王”發(fā)帖數(shù)目超過了帖子總數(shù)的一半。如果你有一個(gè)當(dāng)前論壇上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出這個(gè)傳說中的Tango水王嗎？

分析與解法

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

如果ID列表已經(jīng)是有序的，還需要掃描一遍整個(gè)列表來統(tǒng)計(jì)各個(gè)ID出現(xiàn)的次數(shù)嗎？

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

但上面兩種方法都需要先對(duì)ID列表進(jìn)行排序，時(shí)間復(fù)雜度方面沒有本質(zhì)的改進(jìn)。能否避免排序呢？

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

代碼清單2-8

Type Find(Type* ID, int N)
{
??? Type candidate;
??? int nTimes, i;
??? for(i = nTimes = 0; i < N; i++)
??? {
??????? if(nTimes == 0)
??????? {
???????????? candidate = ID[i], nTimes = 1;
????????}
??????? else
??????? {
????????????if(candidate == ID[i])
??????????????? nTimes++;
??????????? else
??????????????? nTimes--;

??????? }

??? }
????return candidate;
}

在這個(gè)題目中，有一個(gè)計(jì)算機(jī)科學(xué)中很普遍的思想，就是如何把一個(gè)問題轉(zhuǎn)化為規(guī)模較小的若干個(gè)問題。分治、遞推和貪心等都是基于這樣的思路。在轉(zhuǎn)化過程中，小的問題跟原問題本質(zhì)上一致。這樣，我們可以通過同樣的方式將小問題轉(zhuǎn)化為更小的問題。因此，轉(zhuǎn)化過程是很重要的。像上面這個(gè)題目，我們保證了問題的解在小問題中仍然具有與原問題相同的性質(zhì)：水王的ID在ID列表中的次數(shù)超過一半。轉(zhuǎn)化本身計(jì)算的效率越高，轉(zhuǎn)化之后問題規(guī)模縮小得越快，則整體算法的時(shí)間復(fù)雜度越低。

擴(kuò)展問題

隨著Tango的發(fā)展，管理員發(fā)現(xiàn)，“超級(jí)水王”沒有了。統(tǒng)計(jì)結(jié)果表明，有3個(gè)發(fā)帖很多的ID，他們的發(fā)帖數(shù)目都超過了帖子總數(shù)目N的1/4。你能從發(fā)帖ID列表中快速找出他們的ID嗎？

參考上面的解法，思路如下：
如果每次刪除四個(gè)不同的ID（不管是否包含發(fā)帖數(shù)目超過總數(shù)1/4的ID），那么，在剩下的ID列表中，原先發(fā)帖比例大于1/4的ID所占比例仍然大于1/4。可以通過不斷重復(fù)這個(gè)過程，把ID列表中的ID總數(shù)降低（轉(zhuǎn)化為更小的問題），從而得到問題的答案。

代碼如下：

void Find(Type* ID, int N,Type candidate[3])
{
??? Type ID_NULL;//定義一個(gè)不存在的ID
??? int nTimes[3], i;
??? nTimes[0]=nTimes[1]=nTimes[2]=0;
??? candidate[0]=candidate[1]=candidate[2]=ID_NULL;
??? for(i = 0; i < N; i++)
??? {
??????? if(ID[i]==candidate[0])/*先進(jìn)行賦值，i=0時(shí)給第一個(gè)id，i=1時(shí)若id1！=ca0；id1就賦值給ca1，以此循環(huán)，知道times—為0；進(jìn)入time=0的語句中，開始新的循環(huán)，同時(shí)就把原來的id刪掉*/
??????? {
???????????? nTimes[0]++;
??????? }
??????? else if(ID[i]==candidate[1])
??????? {
???????????? nTimes[1]++;
??????? }
??????? else if(ID[i]==candidate[2])
??????? {
???????????? nTimes[2]++;
??????? }
??????? else if(nTimes[0]==0)
??????? {
???????????? nTimes[0]=1;
???????????? candidate[0]=ID[i];
??????? }
??????? else if(nTimes[1]==0)
??????? {
???????????? nTimes[1]=1;
???????????? candidate[1]=ID[i];
??????? }
??????? else if(nTimes[2]==0)
??????? {
???????????? nTimes[2]=1;
???????????? candidate[2]=ID[i];
??????? }
??????? else
??????? {
???????????? nTimes[0]--;
???????????? nTimes[1]--;
???????????? nTimes[2]--;
???????? }
??? }
??? return;
}

總結(jié)

以上是生活随笔為你收集整理的找出发帖的水王问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。