劍指offer 面試題29―數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
來源：程序員人生 發(fā)布時(shí)間：2015-06-08 08:35:13 閱讀次數(shù)：3327次
題目：
數(shù)組中有1個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的1半，請找出這個(gè)數(shù)字。例如輸入1個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的1半，因此輸出2。
解法1：
先將數(shù)組排序，然后出現(xiàn)次數(shù)超過1半的數(shù)字就是a[n/2+1]，時(shí)間復(fù)雜度O(nlgn)。
解法2：O(n)
基本思想：
消除原理：在遍歷數(shù)組的時(shí)候保存兩個(gè)值：1個(gè)是數(shù)組中的1個(gè)數(shù)字，1個(gè)是次數(shù)。當(dāng)我們遍歷到下1個(gè)數(shù)字的時(shí)候，如果下1個(gè)數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加1。如果下1個(gè)數(shù)字和我們之前保存的數(shù)字不同，則次數(shù)減1。如果次數(shù)為零，我們需要保存下1個(gè)數(shù)字，并把次數(shù)設(shè)為1。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那末要找的數(shù)字肯定是最后1次把次數(shù)設(shè)為1時(shí)對應(yīng)的數(shù)字。
固然最后要再遍歷1遍驗(yàn)證這個(gè)數(shù)的出現(xiàn)次數(shù)是不是大于數(shù)組的1半。
#include <iostream>
using namespace std;
bool CheckMoreThanHalf(int a[],int len,int key)
{
int times=0;
for(int i=0;i<len;i++)
{
if(a[i]==key)
times++;
}
bool flag=true;
if(times*2<=len)
flag=false;
return flag;
}
int foo(int a[],int len)
{
if(len<=0)
return ⑴;
int result=a[0];
int times=2;
for(int i=1;i<len;i++)
{
if(times==0)
{
result=a[i];
times=1;
}
else if(a[i]==result)
times++;
else
times--;
}
if(!CheckMoreThanHalf(a,len,result))
result=0;
return result;
}
int main()
{
int a[]={1,2,3,2,2,2,5,4,2};
int b[]={1,2,3,4};
int lenA = sizeof(a)/sizeof(a[0]);
int lenB = sizeof(b)/sizeof(b[0]);
cout<<foo(a,lenA)<<endl;
cout<<foo(b,lenB)<<endl;
return 0;
}
解法3：基于partition函數(shù)，O(n)
基本思想：
如果1個(gè)數(shù)字才數(shù)組中出現(xiàn)的次數(shù)超過了數(shù)組長度的1半，那末對這個(gè)數(shù)組進(jìn)行排序，位于數(shù)組中間位置的那個(gè)數(shù)就是出現(xiàn)次數(shù)超過1半的那個(gè)數(shù)。對數(shù)組排序的時(shí)間復(fù)雜度是O(nlog(n))，但是對這道題目，還有更好的算法，能夠在時(shí)間復(fù)雜度O(n)內(nèi)求出。我們寫過快速排序算法，其中的Partition()方法是1個(gè)最重要的方法，該方法返回1個(gè)index，能夠保證index位置的數(shù)是已排序完成的，在index左側(cè)的數(shù)都比index所在的數(shù)小，在index右側(cè)的數(shù)都比index所在的數(shù)大。那末本題就能夠利用這樣的思路來解。
-
通過Partition()返回index，如果index==mid，那末就表明找到了數(shù)組的中位數(shù)；如果index<mid，表明中位數(shù)在[index+1,end]之間；如果index>mid，表明中位數(shù)在[start,index⑴]之間。知道最后求得index==mid循環(huán)結(jié)束。
-
根據(jù)求得的index，遍歷1遍數(shù)組，每當(dāng)出現(xiàn)1個(gè)等于index所指向的數(shù)時(shí)time++，最后判斷time是不是大于數(shù)組長度的1半，如果大于則表明index所指向的數(shù)就是所求的數(shù)，如果不是，則表明不存在1個(gè)數(shù)出現(xiàn)的次數(shù)超過數(shù)組長度的1半。
#include <iostream>
using namespace std;
bool CheckMoreThanHalf(int a[],int len,int key)
{
int times=0;
for(int i=0;i<len;i++)
{
if(a[i]==key)
times++;
}
bool flag=true;
if(times*2<=len)
flag=false;
return flag;
}
/*
int par(int a[],int len,int low,int high)
{
int t=a[low];
while(low<high)
{
while(low<high&&a[high]>=t)
high--;
a[low]=a[high];
while(low<high&&a[low]<=t)
low++;
a[high]=a[low];
}
a[low]=t;
return low;
}*/
int par(int a[],int len,int low,int high)
{
int t=a[low];
int i=low,j=high;
while(i!=j)
{
while(i<j&&a[j]>=t) j--;
while(i<j&&a[i]<=t) i++;
if(i<j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
a[low]=a[i];
a[i]=t;
return i;
}
int foo(int a[],int len)
{
if(len<=0)
return ⑴;
int mid = len>>1;
int start=0;
int end=len⑴;
int index=par(a,len,start,end);
while(index!=mid)
{
if(index>mid)
{
end=index⑴;
index=par(a,len,start,end);
}
else
{
start=index+1;
index=par(a,len,start,end);
}
}
int result=a[mid];
if(!CheckMoreThanHalf(a,len,result))
result=0;
return result;
}
int main()
{
int a[]={1,2,3,2,2,2,5,4,2};
int b[]={1,2,3,4};
int lenA = sizeof(a)/sizeof(a[0]);
int lenB = sizeof(b)/sizeof(b[0]);
cout<<foo(a,lenA)<<endl;
cout<<foo(b,lenB)<<endl;
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
