Leetcode:NO.347前K个高频元素堆

题目

给定一个非空的整数数组&＃xff0c;返回其中出现频率前 k 高的元素。

示例 1:输入: nums &＃61; [1,1,1,2,2,3], k &＃61; 2
输出: [1,2]


示例 2:输入: nums &＃61; [1], k &＃61; 1
输出: [1]


提示&＃xff1a;你可以假设给定的 k 总是合理的&＃xff0c;且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一&＃xff0c;换句话说&＃xff0c;数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。


链接&＃xff1a;https://leetcode-cn.com/problems/top-k-frequent-elements

解题记录

• 通过map进行数组中数值的统计
• 取出value进行排序获取到第k个value的值
• 通过比对值得到大于等于value值得key写入数组

/*** &＃64;author: ffzs* &＃64;Date: 2020/9/7 上午7:08*/
public class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> numMap &＃61; new HashMap<>();for (int num : nums) {numMap.compute(num, (key, value)-> value &＃61; value &＃61;&＃61; null? 1: value &＃43;1);}List<Integer> values &＃61; new ArrayList<>(numMap.values());values.sort(Comparator.reverseOrder());int[] res &＃61; new int[k];System.out.println(values);int aim &＃61; values.get(k-1);int i &＃61; 0;for (Map.Entry<Integer, Integer> entry : numMap.entrySet()) {if (entry.getValue() >&＃61; aim) {System.out.println(entry.getValue());res[i] &＃61; entry.getKey();i&＃43;&＃43;;}}return res;}
}class Test {public static void main(String[] args) {Solution solution &＃61; new Solution();int[] nums &＃61; {4,1,-1,2,-1,2,3};System.out.println(Arrays.toString(solution.topKFrequent(nums, 2)));}
}


• 通过对进行排序&＃xff0c;始终维持堆的数量为k&＃xff0c;如果新key的value大于当前最小&＃xff0c;替换

/*** &＃64;author: ffzs* &＃64;Date: 2020/9/7 上午8:07*/
public class Solution2 {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> numMap &＃61; new HashMap<>();for (int num : nums) {numMap.compute(num, (key, value)-> value &＃61; value &＃61;&＃61; null? 1: value &＃43;1);}// 根据值排序PriorityQueue<Integer> heap &＃61; new PriorityQueue<>(Comparator.comparingInt(numMap::get));for (Map.Entry<Integer, Integer> entry : numMap.entrySet()) {if (heap.size() < k) heap.add(entry.getKey());else if (numMap.get(heap.peek()) < entry.getValue()) {heap.poll();heap.add(entry.getKey());}}int[] res &＃61; new int[k];for (int i &＃61; 0; i < k; i&＃43;&＃43;) {res[i] &＃61; heap.poll();}return res;}
}