Leetcode 347: Top K Frequent Elements
程序员文章站
2022-03-07 19:45:07
...
题目描述:给定一个非空整数数组,返回数组中k个出现频率最高的元素
输入: nums = [1,1,1,2,2,3], k = 2
输出:[1,2]
解释:由于对输入的元素按出现频率由高到低排序后是 [1,2,3] 返回k=2个元素,则返回值为[1,2]
思路:
1. HashMap 存储 键值对 : (k, v) = (元素:元素出现的次数)
2. 根据HashMap中每个键对应的值进行 建立堆的工作。 可用优先队列实现
注:
优先队列 基于二叉堆实现的, 二叉堆实际使用数组实现的
package Leetcode.Heap.TopKFrequentElements_347;
import java.util.*;
/**
* leetcode 247
*/
public class Solution2 {
public List<Integer> topKFrequent(int[] nums, int k){
List<Integer> topk_list = new ArrayList<Integer>();
HashMap<Integer, Integer> count = new HashMap<>();
for (int i: nums){
count.put(i, count.getOrDefault(i, 0)+1);
}
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2)->count.get(n1)-count.get(n2));
for (int i: count.keySet()){
heap.add(i);
if (heap.size() > k){
heap.poll();
}
}
while (!heap.isEmpty()){
topk_list.add(heap.poll());
}
Collections.reverse(topk_list);
return topk_list;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
int[] nums = {3, 2,2,1,1,1};
int k = 2;
List<Integer> list = solution2.topKFrequent(nums, 2);
System.out.println(list);
}
}
推荐阅读
-
LeetCode刷题笔记(Top K Frequent Elements)
-
TOP K frequent-elements
-
C++实现LeetCode(347.前K个高频元素)
-
LeetCode 692. Top K Frequent Words
-
Leetcode 692. Top K Frequent Words
-
692. Top K Frequent Words
-
LeetCode 347: 前 K 个高频元素 Top K Frequent Elements
-
Top K Frequent Elements
-
(Java)leetcode-347 Top K Frequent Elements
-
[Leetcode] Top K Frequent Elements