从零学算法347

本文主要是介绍从零学算法347，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

347.给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]

• 思路就是记录每个数出现的个数，然后取出现频率前 k 高的数，无非就是使用的方法不同。这里先用 HashMap 记录每个数出现次数，再用优先队列根据出现次数降序排序，最后取前 k 个

•   public int[] topKFrequent(int[] nums, int k) {//先统计每个数字出现的次数Map<Integer, Integer> map = new HashMap<>();for (int num : nums)map.put(num, map.getOrDefault(num, 0) + 1);//最大堆PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);for (int key : map.keySet())priorityQueue.add(new int[]{key, map.get(key)});//取堆中最大的k个元素int[] res = new int[k];for (int i = 0; i < k; i++)res[i] = priorityQueue.poll()[0];return res;}
  

• 用最小堆也差不多同理，只是往堆中添加元素时如果堆的长度大于 k 就移除堆顶元素即可（移除出现次数不够多的）。

•   public int[] topKFrequent(int[] nums, int k) {//先统计每个数字出现的次数Map<Integer, Integer> map = new HashMap<>();for (int num : nums)map.put(num, map.getOrDefault(num, 0) + 1);//最小堆PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);for (int key : map.keySet()) {priorityQueue.add(new int[]{key, map.get(key)});if (priorityQueue.size() > k)priorityQueue.poll();}//把堆中的元素转化为数组int[] res = new int[k];int index = 0;while (!priorityQueue.isEmpty()) {res[index++] = priorityQueue.poll()[0];}return res;}
  

这篇关于从零学算法347的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---