【題目要求】給你n個數與n?，F在需要你在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；
以下是代碼實現，由于題目保證結果一定存在，所以我們省去了最后一步的檢查驗證。
關鍵代碼如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#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%)的數，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網站的支持！
