求出數(shù)組中超過一半的數(shù)

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

創(chuàng)新互聯(lián)公司主要為客戶提供服務(wù)項目涵蓋了網(wǎng)頁視覺設(shè)計、VI標志設(shè)計、成都全網(wǎng)營銷、網(wǎng)站程序開發(fā)、HTML5響應(yīng)式成都網(wǎng)站建設(shè)、成都手機網(wǎng)站制作、微商城、網(wǎng)站托管及成都網(wǎng)站改版、WEB系統(tǒng)開發(fā)、域名注冊、國內(nèi)外服務(wù)器租用、視頻、平面設(shè)計、SEO優(yōu)化排名。設(shè)計、前端、后端三個建站步驟的完善服務(wù)體系。一人跟蹤測試的建站服務(wù)標準。已經(jīng)為成都紙箱行業(yè)客戶提供了網(wǎng)站開發(fā)服務(wù)。

思路：首先想到的是一個最直接的方法，我們可以對所有 ID 進行排序。然后再掃描一遍排好序的 ID 列表，統(tǒng)計各個 ID 出現(xiàn)的次數(shù)。如果某個 ID 出現(xiàn)的次數(shù)超過總數(shù)的一半，那么就輸出這個 ID。這個算法的時間復(fù)雜度為 O（N * log2N + N）。如果 ID 列表已經(jīng)是有序的，還需要掃描一遍整個列表來統(tǒng)計各個 ID 出現(xiàn)的次數(shù)嗎？
如果一個 ID 出現(xiàn)的次數(shù)超過總數(shù) N 的一半。那么，無論水王的 ID 是什么，這個有序的 ID 列表中的第 N/2 項（從 0 開始編號）一定會是這個 ID（讀者可以試著證明一下）。省去重新掃描一遍列表， 可以節(jié)省一點算法耗費的時間。如果能夠迅速定位到列表的某一項 （比如使用數(shù)組來存儲列表），除去排序的時間復(fù)雜度，后處理需要的時間為 O（1）。但上面兩種方法都需要先對 ID 列表進行排序，時間復(fù)雜度方面沒有本質(zhì)的改進。能否避免排序呢

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

#include
using namespace std;
//類比為一個數(shù)組中超過一半的數(shù)，求出這個數(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ǎng)頁題目：求出數(shù)組中超過一半的數(shù)            

            網(wǎng)頁網(wǎng)址：http://m.jiaotiyi.com/article/geisjd.html