快捷導(dǎo)航

出現(xiàn)次數(shù)超過(guò)一半(50%)的數(shù)

更新時(shí)間：2016年07月05日 10:19:29 作者：LJX李家鑫

給出n個(gè)數(shù)，需要我們找出出現(xiàn)次數(shù)超過(guò)一半的數(shù)，下面小編給大家分享下我的實(shí)現(xiàn)思路及關(guān)鍵代碼，感興趣的朋友一起學(xué)習(xí)吧

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

【開(kāi)始胡扯】一開(kāi)始我看到這道題瞬間蒙蔽(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ù)開(kāi)始遍歷，現(xiàn)在給一個(gè)例子，如：1000012，現(xiàn)在進(jìn)行排序：0000112，從0開(kāi)始，設(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)鍵代碼如下所示：

#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ǎng)站的支持！

您可能感興趣的文章: