劍指offer 面試題29―數組中出現次數超過一半的數字
來源：程序員人生 發布時間：2015-06-08 08:35:13 閱讀次數：3322次
題目：
數組中有1個數字出現的次數超過數組長度的1半，請找出這個數字。例如輸入1個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的1半，因此輸出2。
解法1：
先將數組排序，然后出現次數超過1半的數字就是a[n/2+1]，時間復雜度O(nlgn)。
解法2：O(n)
基本思想：
消除原理：在遍歷數組的時候保存兩個值：1個是數組中的1個數字，1個是次數。當我們遍歷到下1個數字的時候，如果下1個數字和我們之前保存的數字相同，則次數加1。如果下1個數字和我們之前保存的數字不同，則次數減1。如果次數為零，我們需要保存下1個數字，并把次數設為1。由于我們要找的數字出現的次數比其他所有數字出現的次數之和還要多，那末要找的數字肯定是最后1次把次數設為1時對應的數字。
固然最后要再遍歷1遍驗證這個數的出現次數是不是大于數組的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函數，O(n)
基本思想：
如果1個數字才數組中出現的次數超過了數組長度的1半，那末對這個數組進行排序，位于數組中間位置的那個數就是出現次數超過1半的那個數。對數組排序的時間復雜度是O(nlog(n))，但是對這道題目，還有更好的算法，能夠在時間復雜度O(n)內求出。我們寫過快速排序算法，其中的Partition()方法是1個最重要的方法，該方法返回1個index，能夠保證index位置的數是已排序完成的，在index左側的數都比index所在的數小，在index右側的數都比index所在的數大。那末本題就能夠利用這樣的思路來解。
-
通過Partition()返回index，如果index==mid，那末就表明找到了數組的中位數；如果index<mid，表明中位數在[index+1,end]之間；如果index>mid，表明中位數在[start,index⑴]之間。知道最后求得index==mid循環結束。
-
根據求得的index，遍歷1遍數組，每當出現1個等于index所指向的數時time++，最后判斷time是不是大于數組長度的1半，如果大于則表明index所指向的數就是所求的數，如果不是，則表明不存在1個數出現的次數超過數組長度的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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
