代码：
/*
数组中出现次数超过一半的数字
by Rowandjj
2014/8/9
*/
#include<iostream>
using namespace std;
bool isValid = false;
//检查数组是否合法
bool CheckInvalidArray(int arr[],int len)
{
isValid = false;
if(arr == NULL || len <= 0)
{
isValid = true;
}
return isValid;
}
//检查num出现次数是否超过数组一半
bool CheckMoreThanHalf(int arr[],int len,int num)
{
int times = 0;
for(int i = 0; i < len; i++)
{
if(arr[i] == num)
{
times++;
}
}
bool isMoreThanHalf = true;
if(times*2 <= len)
{
isMoreThanHalf = false;
isValid = true;
}
return isMoreThanHalf;
}
//解法1：先对数组进行排序，然后中间的那个数就是出现次数超过一半的数字(O(nLogn))
int partition(int arr[],int low,int high)
{
int val = arr[low];
while(low < high)
{
while(low < high && arr[high] >= val)
{
high--;
}
arr[low] = arr[high];
while(low < high && arr[low] <= val)
{
low++;
}
arr[high] = arr[low];
}
arr[low] = val;
return low;
}
//快排
void QuickSort(int arr[],int low,int high)
{
if(arr == NULL || low >= high)
{
return;
}
int index = partition(arr,low,high);
QuickSort(arr,low,index-1);
QuickSort(arr,index+1,high);
}
int MoreThanHalfNum(int arr[],int len)
{
if(CheckInvalidArray(arr,len))
{
return -1;
}
QuickSort(arr,0,len-1);
if(!CheckMoreThanHalf(arr,len,arr[len/2]))
{
return -1;
}
return arr[len/2];
}
/*
解法2：
数组中一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有
数字出现的次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值，
一个是数组中的一个数字，一个是次数，当我们遍历到下一个数字的时候，如果下一个数字
和我们之前保存的数字相同，则次数加1，如果下一个数字和我们之前保存的数字不同，那么
次数减1，如果次数为0，我们需要保存下一个数字，并把次数设置为1.
*/
int MoreThanHalfNum_2(int arr[],int len)
{
if(CheckInvalidArray(arr,len))
{
return -1;
}
int result = arr[0];
int times = 1;
for(int i = 1; i < len; i++)
{
if(times == 0)
{
result = arr[i];
times = 1;
}else if(arr[i] == result)
{
times++;
}else
{
times--;
}
}
if(!CheckMoreThanHalf(arr,len,result))
{
return -1;
}
return result;
}
int main()
{
int arr[] = {1,2,3,2,2,2,2,5,4};
//int result = MoreThanHalfNum(arr,9);
int result = MoreThanHalfNum_2(arr,9);
if(isValid)
{
cout<<"Invalid Input"<<endl;
}else
{
cout<<result<<endl;
}
return 0;
}