题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这一个数字。输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}，
数字2在数组中出现的次数大于数组长度的一半，返回2。
这道题类似以前做过的
Maximum Subarray。
按着以前的思路：
确定某一个数字，遇到相同的数字加1，遇到不同的数字减1，当累加器为0时，我们重新开始计算即可。
完成后继续判断这个数字有没有出现够一定的次数。
代码如下
public static int moreHalfSimple(int[] num)
{
int count =1;
int index;
int result=num[0];
for(index = 1;index<num.length-1;index++)
{
if(count==0)
{
result = num[index];
count=1;
}
if(result != num[index])
count--;
else
count++;
}
if(!checkHalf(num,result))
{
result=-1;//没找到返回-1
}
return result;
}
//判断数字是否出现了数组一半以上的长度
private static boolean checkHalf(int[] num, int result) {
int count=0;
for(int i =0;i<num.length;i++)
{
if(num[i] == result)
count++;
}
if(count*2 <=num.length)
return false;
return true;
}
----------------------------------------------------------------------------------------------------------------------------------------------
看了剑指Offer上面还有一种解法，特意贴上来：
它的思路是：
如果一个数组元素出现的次数大于数组长度的一半，那么这个数组排序后，这个数肯定位于数组中间。即中位数。
我们借用快排的思想，如果最终和轴交换的元素处于数组的中间，那么我们继续判断这个数字是否出现了大于一半的次数。
代码如下：
private static int partition(int []num,int start,int end)
{
if(num==null || num.length ==0)
return -1;
int s = num[end];
int minIndex=start-1;
int maxIndex=start;
for(;maxIndex<end;maxIndex++)
{
if(num[maxIndex] <= num[end])
{
minIndex++;
swap(num,minIndex,maxIndex);
}
}
swap(num,minIndex+1,maxIndex);
return minIndex+1;
}
private static void swap(int[] num ,int a ,int b)
{
int temp = num[a];
num[a] = num[b];
num[b] = temp;
}
static boolean inputflag= false;//全局变量记录是输入无效还是没找到
public static int moreThanhalf(int[] num,int start,int end)
{
if(num ==null || num.length==0 ||start>end)
{
inputflag=true;
return -1; inputflag为true且返回-1，说明输入无效
}
int result=0;
int middle = num.length >> 1;
int index;
index = partition(num, start, end);
while(index != middle)
{
if(index>middle)
{
index =partition(num, start, index-1);
}
else
{
index = partition(num, index+1, end);
}
}
result = num[middle];
if(!checkHalf(num,result))
{
result =0;//返回0且inputFlag为false说明没找到
}
return result;
}
private static boolean checkHalf(int[] num, int result) {
int count=0;
for(int i =0;i<num.length;i++)
{
if(num[i] == result)
count++;
}
if(count*2 <=num.length)
{ inputflag=false;
return false;
}
return true;
}