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 水王嗎？

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：申請(qǐng)域名、網(wǎng)站空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、賓陽(yáng)網(wǎng)站維護(hù)、網(wǎng)站推廣。

思路：首先想到的是一個(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* log2N+ N）。如果 ID 列表已經(jīng)是有序的，還需要掃描一遍整個(gè)列表來(lái)統(tǒng)計(jì)各個(gè) ID 出現(xiàn)的次數(shù)嗎？
如果一個(gè) ID 出現(xiàn)的次數(shù)超過總數(shù) N的一半。那么，無(wú)論水王的 ID 是什么，這個(gè)有序的 ID 列表中的第 N/2 項(xiàng)（從 0 開始編號(hào)）一定會(huì)是這個(gè) ID（讀者可以試著證明一下）。省去重新掃描一遍列表， 可以節(jié)省一點(diǎn)算法耗費(fèi)的時(shí)間。如果能夠迅速定位到列表的某一項(xiàng) （比如使用數(shù)組來(lái)存儲(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)存。

#include
using namespace std;
//類比為一個(gè)數(shù)組中超過一半的數(shù)，求出這個(gè)數(shù) 
template
T Find(T* a,int size)
{
	T ret=-1;
	int time=0;
	for(int i=0;i
參照：https://github.com/xiaozhi1995/SmartCode/blob/master/20160511702SearchMidNum/main.cpp
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
            

            本文名稱：求出數(shù)組中超過一半的數(shù)-創(chuàng)新互聯(lián)            

            分享網(wǎng)址：http://weahome.cn/article/cseehc.html