# 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

//方案一

import java.util.*;

public class Solution {

``````public int MoreThanHalfNum_Solution(int [] array) {

int len=array.length;
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();

for(int i=0;i<len;i++){

if(!hash.containsKey(array[i]))
hash.put(array[i],1);
else
hash.put(array[i], hash.get(array[i]) + 1);

if(hash.get(array[i])*2>len)
return array[i];
}

return 0;
}
``````

}

//方案二 网友称为分形叶的思想

import java.util.*;

public class Solution { public int MoreThanHalfNum_Solution(int [] array) {

``````    int len=array.length;

int result = array[0];
int time=1;

for(int i=1;i<len;i++)
{
if(time==0){
time=1;
result=array[i];
}else
if(result==array[i])
time++;
else
time--;
}

int sum=0;
for(int i=0;i<len;i++)
if(array[i]==result)
sum++;

if(sum*2>len)
return result;
else
return 0;

}
``````

}

//方案三：

import java.util.*;

public class Solution {

``````public int MoreThanHalfNum_Solution(int [] array) {

int len=array.length;

int mid=len/2;

int start=0;
int end=len-1;
int index = f(array,start,end);

while(index!=mid){
if(index>mid)
index=f(array,start,index-1);
else
index=f(array,index+1,end);
}

int result=array[mid];
int sum=0;

for(int i=0;i<len;i++)
if(result==array[i])
sum++;

return sum*2>len?result:0;

}

public int f(int input[],int begin,int end){

int low = begin;
int high = end;
int pivot = input[low];
while (low < high)
{
while (low < high&&pivot <= input[high])
high--;

input[low] = input[high];
while (low < high&&pivot >= input[low])
low++;
input[high] = input[low];
}
input[low] = pivot;
return low;

}
``````

}