算法--找出數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)
???? 每當(dāng)我看到經(jīng)典的算法題，就懷念高中，感覺很多算法題就是高中的題目，誰叫哥只讀了個(gè)專科，高數(shù)基本相當(dāng)沒學(xué)。
???? 有空要看看高數(shù)啊，想當(dāng)年數(shù)學(xué)那是相當(dāng)?shù)?.....

#include <iostream>
using namespace std;
class FindTheOne
{
public:
??方法一
? 第一個(gè)想到的方法是見一個(gè)二維數(shù)組，一維存數(shù)組中的數(shù)據(jù)，二維存這個(gè)數(shù)出現(xiàn)的次數(shù)。出現(xiàn)次數(shù)最多的那個(gè)數(shù)就是要找的那個(gè)數(shù)
? 由于某個(gè)數(shù)出現(xiàn)的次數(shù)超過數(shù)組長度的一半，所以二維數(shù)組的長度只需要這個(gè)數(shù)組的一半。代碼實(shí)現(xiàn)如下，
? 當(dāng)然這個(gè)方法很糟糕，時(shí)間復(fù)雜度和空間復(fù)雜度都比較大，想練手的我還是寫了一下。

　　

void?Search(int?A[],int?len,int&?theOne)
{
if(NULL==A?||?len<=0)
{
return?;
}

int?(*B)[2]=newint[len/2][2];
B[0][0]=A[0];
B[0][1]=1;

int?t=0;
bool?notExist=true;
for(int?i=1;i<len;++i)
{
for(int?j=0;j<t;++j)
{
if(A[i]==B[j][0])
{
B[j][1]++;
notExist=false;
break;
}
}
if(notExist)
{
B[t++][0]=A[i];
}
}

int?max=1;
int?k=0;
for(int?i=0;i<len/2;++i)
{
if(B[i][1]>max)
{
max=B[i][1];
k=i;
}
}

theOne=B[k][0];
}

方法二
???? 將數(shù)組排序，最中間的那個(gè)數(shù)就是您要找的數(shù)。
?? ? 如果出現(xiàn)最多的那個(gè)數(shù)是最小的，那么1至(n+1)/2都是那個(gè)數(shù)
???? 如果出現(xiàn)最多的那個(gè)數(shù)是最大的，那么(n-1)/2至n都是那個(gè)數(shù)
???? 如果不是最小也不是最大，當(dāng)這個(gè)數(shù)由最小慢慢變成最大的最大的數(shù)時(shí)，你會(huì)發(fā)現(xiàn)中間的那個(gè)數(shù)的值是不變的。
???? 綜上所述，中間的那個(gè)數(shù)就是你要找的那個(gè)數(shù)。
???? 時(shí)間復(fù)雜度就是你排序用的時(shí)間。排序真的不想寫了（可以參考《我的另一篇博客》）。大家都知道排序還是相當(dāng)費(fèi)時(shí)的，當(dāng)然這個(gè)方法還是不太好。

?方法三
???? 這個(gè)方法借用了別人的思路。
???? 在這里我做一下簡(jiǎn)單的分析。
???? 這個(gè)算法的時(shí)間復(fù)雜度是O(n)，另外用了兩個(gè)輔助變量。
???? k用于臨時(shí)存儲(chǔ)數(shù)組中的數(shù)據(jù)，j用于存儲(chǔ)某個(gè)數(shù)出現(xiàn)的次數(shù)。
???? 開始時(shí)k存儲(chǔ)數(shù)組中的第一個(gè)數(shù),j為0，如果數(shù)組出現(xiàn)的數(shù)于k相等，則j加1，否則就減1，如果j為0，就把當(dāng)前數(shù)組中的數(shù)賦給k
???? 因?yàn)橹付ǖ臄?shù)出現(xiàn)的次數(shù)大于數(shù)組長度的一半，所有j++與j--相抵消之后，最后j的值是大于等于1的，k中存的那個(gè)數(shù)就是出現(xiàn)最多的那個(gè)數(shù)。

??? 下面這個(gè)算法只適合數(shù)組中數(shù)組中某個(gè)數(shù)的出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)組，符合題意。

int?Search(int?A[],int?len)
{
if(NULL==A?||?len<=0)
{
return-1;
}

int?k, j=0;
for(int?i=0;i<len;++i)
{
if(j==0)
{
k=A[i];
}
if(k==A[i])
{
++j;//有人說++j比j++有先天的優(yōu)勢(shì)，不知你是否聽說，如果你也聽說，有沒有想過More Effective C++(C++程序員必看書籍)
}else
{
--j;
}
}

return?k;
}

總結(jié)

以上是生活随笔為你收集整理的找出数组中出现次数超过一半的数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。