代码随想录 347.前K个高频元素

题目要求返回前k个频率最大的元素联想到堆无需对k频率之后的元素进行处理进一步优化了时间复杂度。具体步骤1.借助哈希表建立数字和其出现次数的映射遍历一遍数组统计元素的频率。//用map来存储nums[]中各个数字出现的个数 MapInteger,Integer map new HashMap(); for(int num:nums) { if(map.containsKey(num)){ map.put(num,map.get(num)1); }else{ map.put(num,1); } }2.维护一个元素数目为k的最小堆。//map.get(a) - map.get(b)是小根堆map.get(b) - map.get(a)是大根堆 PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger() { Override public int compare(Integer a, Integer b) { return map.get(a)-map.get(b); } });3.每次都将新元素与堆顶元素堆中频率最小的元素进行比较。4.如果新的元素的频率比堆顶端的元素大则弹出堆顶端的元素将新的元素添加进堆中。5.最终堆中的k个元素即为前k个高频元素。Java的集合框架如HashMap、ArrayList等只能存储对象类型不能直接存储基本类型int、char、boolean等所以必须使用它们的包装类int - Integer、char - Character、boolean - Boolean。所以后面取key时比较的key的类型都是对象类型Integer用Integer来取。附代码class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger,Integer mp new HashMap(); for(int num : nums){ if(mp.containsKey(num)){ mp.put(num,mp.get(num) 1); }else{ mp.put(num,1); } } PriorityQueueInteger heap new PriorityQueue(new ComparatorInteger(){ // Override public int compare(Integer a,Integer b){ return mp.get(a) - mp.get(b); } }); for(Integer key : mp.keySet()){ if(heap.size()k){ heap.add(key); }else if(mp.get(key) mp.get(heap.peek())){ heap.remove(); heap.add(key); } } int[] res new int[k]; for(int i 0;ik;i){ res[i] heap.remove(); } return res; } }