数组中出现次数超过一半的数字-蒲公英云

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

链接： https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
来源：牛客网

热度指数：120162时间限制：1秒空间限制：32768K

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

分析：采用HashMap值对，因为key是唯一的，所以map中的key存放的都会是数组中所有的数字（不会重复）。其中key为数组中的数组，value为数组中数字出现的次数。循环遍历数组，将数组中的数字即该数字出现的次数存入map，若数字位加入map中，则将该数字加入map中，次数为1，即map.put(array[i],1)；若数字已在map中，则将该数字对应的重新加入map中，出现的次数加1，即map.put(array[i],map.get(array[i]) + 1)。把数组中的所有数字即出现次数加入map中后，循环map，获取key对应的value值，若value值大于数组array长度的一半，则key就是我们要找的数字，直接返回即可。若未找到，最后返回0。

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         if(array == null || array.length == 0)
            return 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        //HashSet<Integer> sets = new HashSet<Integer>();
        for(int i = 0;i < array.length;i++){
            //sets.add(array[i])
            //int count = 1;
            if(map.containsKey(array[i]))
                map.put(array[i],map.get(array[i]) + 1);
            else
                map.put(array[i],1);
        }
        Iterator iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            if(array.length < (int) entry.getValue() * 2)
                return (int) entry.getKey();
        }
        return 0;
    }
}