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

//方案一

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;
    
}

}

推荐方案二，方案其实很差，但是提供了一个球第k大数的思路