【題目要求】給你n個(gè)數(shù)與n。現(xiàn)在需要你在O(n)的時(shí)間內(nèi)，O(1)的空間內(nèi)找出出現(xiàn)次數(shù)超過(guò)50%的數(shù)。
【開始胡扯】一開始我看到這道題瞬間蒙蔽(ToT)/~~~(。﹏。*)，要是只有O(n)的時(shí)間這一條要求，就可以用哈希瞬間解決（也就是用空間換時(shí)間），對(duì)于O(1)的空間好像很難解決。
【思路一】雙重循環(huán)，這是解決這道題效率最低的方法了，也就是對(duì)每個(gè)數(shù)都計(jì)算它出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度 O(n^2) 直接Out。
【思路二】先排序，讓相近的數(shù)字排在一起，然后從第一個(gè)數(shù)開始遍歷，現(xiàn)在給一個(gè)例子，如：1000012，現(xiàn)在進(jìn)行排序：0000112，從0開始，設(shè)定一個(gè)計(jì)數(shù)器T=0，現(xiàn)在有4個(gè)0，則T=4，發(fā)現(xiàn)超過(guò)了半數(shù)，輸出0。這個(gè)方法就是上一個(gè)方法的優(yōu)化版，Out。
【思路三】就是以空間換時(shí)間，哈希的思想，使一個(gè)一維數(shù)組有兩個(gè)含義。比如a[x]=y代表x這個(gè)數(shù)出現(xiàn)了y次，這個(gè)方法時(shí)間復(fù)雜度是O(n)，但是空間實(shí)在是……不說(shuō)了(* ￣︿￣) Out
【思路四】先算出概率，選出這些數(shù)中最有可能符合要求的幾個(gè)數(shù)，再隨機(jī)抽取幾個(gè)。這……還是算了吧。
【思路五】今天的主題，就是所謂的MJRTY算法，也叫多數(shù)投票算法，主要思路如下:（這個(gè)算法時(shí)間復(fù)雜度O(n)！空間上不需要額外的儲(chǔ)存，所以空間復(fù)雜度是O(1)!!!!!!）
如果count==0，則將vote的值設(shè)置為數(shù)組的當(dāng)前元素，將count賦值為1；
否則，如果vote和現(xiàn)在數(shù)組元素值相同，則count++，反之count–；
重復(fù)上述兩步，直到掃描完數(shù)組。
count賦值為0，再次從頭掃描數(shù)組，如果數(shù)組元素值與vote的值相同則count++，直到掃描完數(shù)組為止。
如果此時(shí)count的值大于等于n/2，則返回vote的值，反之則返回-1；
以下是代碼實(shí)現(xiàn)，由于題目保證結(jié)果一定存在，所以我們省去了最后一步的檢查驗(yàn)證。
關(guān)鍵代碼如下所示：
|
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;} |
以上所述是小編給大家介紹的出現(xiàn)次數(shù)超過(guò)一半(50%)的數(shù)，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)服務(wù)器之家網(wǎng)站的支持！
