Top K Frequent Elements
2024-04-06 09:33:45
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
分析：
http://blog.csdn.net/itismelzp/article/details/51451374
bucket sort, 出现次数作为被sort的对象。
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// worst case, all values in nums are the same.
// Therefore, the size of buckets should be nums.length + 1
List<Integer>[] bucket = new List[nums.length + ];
for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
}
for (int key : map.keySet()) {
int value = map.get(key);
if (bucket[value] == null) {
bucket[value] = new ArrayList<Integer>();
}
bucket[value].add(key);
}
List<Integer> res = new ArrayList<Integer>();
for (int i = bucket.length - ; i >= && res.size() < k; i--) {
if (bucket[i] != null) {
res.addAll(bucket[i]);
}
}
return res;
}
}
使用min heap.
class Pair {
int num;
int count;
public Pair(int num, int count) {
this.num = num;
this.count = count;
}
}
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// count the frequency for each element
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
}
// create a min heap
PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.count - b.count;
}
});
// maintain a heap of size k.
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Pair p = new Pair(entry.getKey(), entry.getValue());
queue.offer(p);
if (queue.size() > k) {
queue.poll();
}
}
// get all elements from the heap
List<Integer> result = new ArrayList<Integer>();
while (queue.size() > ) {
result.add(queue.poll().num);
}
// reverse the order
Collections.reverse(result);
return result;
}
}
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// count the frequency for each element
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
}
// create a min heap
Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) {
return a.getValue() - b.getValue();
}
});
// maintain a heap of size k.
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
queue.offer(entry);
if (queue.size() > k) {
queue.poll();
}
}
// get all elements from the heap
List<Integer> result = new ArrayList<Integer>();
while (queue.size() > ) {
result.add(queue.poll().getKey());
}
// reverse the order
Collections.reverse(result);
return result;
}
}
最新文章
- Leetcode: Palindrome Partitioning II
- 配置容器configuring Containsers
- [NOIP2011] 聪明的质检员（二分答案）
- window下flask开发环境搭建
- C# 7.0 新特性3： 模式匹配
- 浅谈AJAX的基本原理和原生AJAX的基础用法
- ionic-native-transitions调用原生页面切换实现ionic路由切换
- CSSの神小结-简单备忘一下(亲测可用)
- 【风马一族_Android】强制activity的横屏与纵屏
- Mysql分表和分区的区别
- centos 6.0中文输入法的设置
- 使用Tomcat-redis-session-manager来实现Tomcat集群部署中的Session共享
- BZOJ 2809: [Apio2012]dispatching [斜堆]
- php实现记住密码自动登录的功能
- Java之String类型详解
- iOS中 CocoaPods Mac App的安装和使用 韩俊强的博客
- Docker在Linux上运行NetCore系列（三）在Linux上使用Docker运行Asp.NetCore
- [NLP] 酒店名归类
- python之OpenCv(三)---基本绘图
- vue 中结合百度地图获取当前城市