湧現次數跨越一半(50%)的數。本站提示廣大學習愛好者：（湧現次數跨越一半(50%)的數）文章只能為提供參考，不一定能成為您想要的結果。以下是湧現次數跨越一半(50%)的數正文
【標題請求】給你n個數與n。如今須要你在O(n)的時光內，O(1)的空間內找出湧現次數跨越50%的數。
【開端胡扯】一開端我看到這道題剎時蒙蔽(ToT)/~~~(。﹏。*)，如果只要O(n)的時光這一條請求，便可以用哈希剎時處理（也就是用空間換時光），關於O(1)的空間似乎很難處理。
【思緒一】兩重輪回，這是處理這道題效力最低的辦法了，也就是對每一個數都盤算它湧現的次數，時光龐雜度 O(n^2) 直接Out。
【思緒二】先排序，讓鄰近的數字排在一路，然後從第一個數開端遍歷，如今給一個例子，如：1000012，如今停止排序：0000112，從0開端，設定一個計數器T=0，如今有4個0，則T=4，發明跨越了折半，輸入0。這個辦法就是上一個辦法的優化版，Out。
【思緒三】就是以空間換時光，哈希的思惟，使一個一維數組有兩個寄義。好比a[x]=y代表x這個數湧現了y次，這個辦法時光龐雜度是O(n)，然則空間其實是……不說了(* ￣︿￣) Out
【思緒四】先算出幾率，選出這些數中最有能夠相符請求的幾個數，再隨機抽取幾個。這……照樣算了吧。
【思緒五】明天的主題，就是所謂的MJRTY算法，也叫多半投票算法，重要思緒以下:（這個算法時光龐雜度O(n)！空間上不須要額定的貯存，所以空間龐雜度是O(1)!!!!!!）
假如count==0，則將vote的值設置為數組確當前元素，將count賦值為1；
不然，假如vote和如今數組元素值雷同，則count++，反之count–；
反復上述兩步，直到掃描完數組。
count賦值為0，再次從頭掃描數組，假如數組元素值與vote的值雷同則count++，直到掃描完數組為止。
假如此時count的值年夜於等於n/2，則前往vote的值，反之則前往-1；
以下是代碼完成，因為標題包管成果必定存在，所以我們省去了最初一步的檢討驗證。
症結代碼以下所示：
#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;
}
以上所述是小編給年夜家引見的湧現次數跨越一半(50%)的數，願望對年夜家有所贊助，假如年夜家有任何疑問請給我留言，小編會實時答復年夜家的。在此也異常感激年夜家對網站的支撐！
