算法--找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)

作者：陳太漢

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

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

方法一

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í)間。排序真的不想寫(xiě)了（可以參考《我的另一篇博客》）。大家都知道排序還是相當(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ù)。
     開(kāi)始時(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ù)組長(zhǎng)度的一半，所有j++與j--相抵消之后，最后j的值是大于等于1的，k中存的那個(gè)數(shù)就是出現(xiàn)最多的那個(gè)數(shù)。

    下面這個(gè)算法只適合數(shù)組中數(shù)組中某個(gè)數(shù)的出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(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;//有人說(shuō)++j比j++有先天的優(yōu)勢(shì)，不知你是否聽(tīng)說(shuō)，如果你也聽(tīng)說(shuō)，有沒(méi)有想過(guò)More Effective C++(C++程序員必看書(shū)籍)
}else
{
--j;
}
}

return k;
}

};