题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
解法一：
先将数组排序，然后出现次数超过一半的数字就是a[n/2+1]，时间复杂度O(nlgn)。
解法二：O(n)
基本思想：
当然最后要再遍历一遍验证这个数的出现次数是否大于数组的一半。
#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 -1;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++;elsetimes–;}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;}
解法三：基于partition函数，O(n)
基本思想：
如果一个数字才数组中出现的次数超过了数组长度的一半，那么对这个数组进行排序，位于数组中间位置的那个数就是出现次数超过一半的那个数。对数组排序的时间复杂度是O(nlog(n))，，但是对于这道题目，还有更好的算法，能够在时间复杂度O(n)内求出。我们写过快速排序算法，其中的Partition()方法是一个最重要的方法，该方法返回一个index，能够保证index位置的数是已排序完成的，在index左边的数都比index所在的数小，在index右边的数都比index所在的数大。那么本题就可以利用这样的思路来解。
通过Partition()返回index，如果index==mid，那么就表明找到了数组的中位数；如果index<mid，表明中位数在[index+1,end]之间；如果index>mid，表明中位数在[start,index-1]之间。知道最后求得index==mid循环结束。根据求得的index，遍历一遍数组，每当出现一个等于index所指向的数时time++，最后判断time是否大于数组长度的一半，如果大于则表明index所指向的数就是所求的数，如果不是，则表明不存在一个数出现的次数超过数组长度的一半。#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 -1;int mid = len>>1;int start=0;int end=len-1;int index=par(a,len,start,end);while(index!=mid){if(index>mid){end=index-1;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;}
长江后浪催前浪，一辈新人换旧人。
