【題目要求】給你n個數(shù)與n。現(xiàn)在需要你在O(n)的時間內(nèi)，O(1)的空間內(nèi)找出出現(xiàn)次數(shù)超過50%的數(shù)。

【開始胡扯】一開始我看到這道題瞬間蒙蔽(ToT)/~~~(。﹏。*)，要是只有O(n)的時間這一條要求，就可以用哈希瞬間解決（也就是用空間換時間），對于O(1)的空間好像很難解決。

【思路一】雙重循環(huán)，這是解決這道題效率最低的方法了，也就是對每個數(shù)都計算它出現(xiàn)的次數(shù)，時間復雜度 O(n^2) 直接Out。

【思路二】先排序，讓相近的數(shù)字排在一起，然后從第一個數(shù)開始遍歷，現(xiàn)在給一個例子，如：1000012，現(xiàn)在進行排序：0000112，從0開始，設定一個計數(shù)器T=0，現(xiàn)在有4個0，則T=4，發(fā)現(xiàn)超過了半數(shù)，輸出0。這個方法就是上一個方法的優(yōu)化版，Out。

【思路三】就是以空間換時間，哈希的思想，使一個一維數(shù)組有兩個含義。比如a[x]=y代表x這個數(shù)出現(xiàn)了y次，這個方法時間復雜度是O(n)，但是空間實在是……不說了(* ￣︿￣) Out

【思路四】先算出概率，選出這些數(shù)中最有可能符合要求的幾個數(shù)，再隨機抽取幾個。這……還是算了吧。

【思路五】今天的主題，就是所謂的MJRTY算法，也叫多數(shù)投票算法，主要思路如下:（這個算法時間復雜度O(n)！空間上不需要額外的儲存，所以空間復雜度是O(1)!!!!!!）

如果count==0，則將vote的值設置為數(shù)組的當前元素，將count賦值為1；

否則，如果vote和現(xiàn)在數(shù)組元素值相同，則count++，反之count–；

重復上述兩步，直到掃描完數(shù)組。

count賦值為0，再次從頭掃描數(shù)組，如果數(shù)組元素值與vote的值相同則count++，直到掃描完數(shù)組為止。

如果此時count的值大于等于n/2，則返回vote的值，反之則返回-1；

以下是代碼實現(xiàn)，由于題目保證結果一定存在，所以我們省去了最后一步的檢查驗證。

關鍵代碼如下所示：

#include<iostream>
using namespace std;
int len; 
void Find(int* a, int N) 
{
char candidate;
int nTimes, i;
for(i=nTimes=0;i<N;i++)
{
if(nTimes==0) candidate=a[i],nTimes=1;
else
{
if(candidate==a[i]) nTimes++;
else nTimes--;
}
}
cout<<candidate; 
}
int main()
{
cin>>len;
int a[len];
for(int i=0;i<n;i++) cin>>a[i];
Find(a,len);
system("pause");
return 0;
} 

以上所述是小編給大家介紹的出現(xiàn)次數(shù)超過一半(50%)的數(shù)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！