数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：先把所有出现过的数字和出现的次数以键值对的形式存起来，然后取出现次数和数组的一半值进行比较。

import java.util.HashMap;
import java.util.Set;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int result = 0;
        if(array!=null){
            HashMap<Integer,Integer> map = new HashMap();
            float half = array.length/2;
            for(int value:array){
                if(map.get(value)!=null){
                    map.put(value,map.get(value)+1);
                }else{
                    map.put(value,1);
                }
            }
            Set<Map.Entry<Integer,Integer>> set = map.entrySet();
            for(Map.Entry<Integer,Integer> entry:set){
                if(entry.getValue()>half){
                    return entry.getKey();
                }
            }
        }
        return result;
    }
}

集合实现（面试不记得HashMap的各种方法了可以用来救急）：

import java.util.ArrayList;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int result = 0;
        if(array!=null){
            float half = array.length/2;
            ArrayList<Integer> key = new ArrayList();
            ArrayList<Integer> count = new ArrayList();
            for(int val:array){
                if(!key.contains(val)){
                    key.add(val);
                    count.add(1);
                }else{
                    int index = key.indexOf(val);
                    count.set(index,count.get(index)+1);
                }
            }
            for(int val:count){
                if(val>half){
                    return key.get(count.indexOf(val));
                }
            }

        }
        return result;
    }
}