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

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：申請域名、網站空間、營銷軟件、網站建設、賓陽網站維護、網站推廣。

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

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

#include<iostream>
using namespace std;
//類比為一個數組中超過一半的數，求出這個數 
template<class T>
T Find(T* a,int size)
{
	T ret=-1;
	int time=0;
	for(int i=0;i<size;++i)
	{
		if(time==0)
		{
			ret=a[i];
			++time;
		}
		else
		{
			if(ret!=a[i])
				--time;
			else
				++time;
		}
	}
	return ret;
}

int main()
{
	int a[10]={1,5,2,3,5,7,5,5,5,5};
	cout<<Find(a,10)<<endl;
	return 0;
}

參照：https://github.com/xiaozhi1995/SmartCode/blob/master/20160511702SearchMidNum/main.cpp

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

新聞標題：求出數組中超過一半的數-創新互聯
文章鏈接：http://vcdvsql.cn/article42/cseehc.html

成都網站建設公司_創新互聯，為您提供網站策劃、域名注冊、網站導航、手機網站建設、商城網站、網站維護

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯