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

逃离我推掉我的手 2022-06-07 02:25 148阅读 0赞

链接： [https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163][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,value>值对，因为key是唯一的，所以map中的key存放的都会是数组中所有的数字（不会重复）。其中key为数组中的数组，value为数组中数字出现的次数。循环遍历数组，将数组中的数字即该数字出现的次数存入map，若数字位加入map中，则将该数字加入map中，次数为1，即map.put(array\[i\],1)；若数字已在map中，则将该数字对应的<key,value>重新加入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;
        }
    }

[https_www.nowcoder.com_questionTerminal_e8a1b01a2df14cb2b228b30ee6a92163]: https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163