347. 前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例2:
输入: nums = [1], k = 1
输出: [1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
1. 优先队列
思路：使用一个最小堆
- 遍历数组，将每个元素及其出现的频率存入 map 中
- 创建一个优先队列(最小堆)，先存入 k 个元素
- 如果当前堆中已经有了 k 个元素，则判断下一个元素的频率是否堆顶元素(最小值), 如果大的话，就将最小的元素删除掉，将该元素添加进去
- 遍历该队列，将元素加入 list 即可
private class Freq implements Comparable<Freq> {
int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
@Override
public int compareTo(Freq another) {
return this.freq - another.freq;
// if (this.freq > another.freq) return 1;
// else if (this.freq < another.freq) return -1;
// else return 0;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Freq> heap = new PriorityQueue<>();
for (int key : map.keySet()) {
if (heap.size() < k) {
heap.add(new Freq(key, map.get(key)));
} else if (map.get(key) > heap.peek().freq) {
heap.poll();
heap.add(new Freq(key, map.get(key)));
}
}
List<Integer> list = new LinkedList<>();
while (!heap.isEmpty()) {
list.add(heap.poll().e);
}
return list;
}
复杂度分析：
时间复杂度：O(n + m) = O(n), 时间复杂度为两次遍历所用的时间
空间复杂度：O(n), map所需要的空间
-
2. 优化
思路：优化方法1
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (int key : map.keySet()) {
if (heap.size() < k) {
heap.add(key);
} else if (map.get(key) > map.get(heap.peek())) {
heap.poll();
heap.add(key);
}
}
List<Integer> list = new LinkedList<>();
while (!heap.isEmpty()) {
list.add(heap.poll() );
}
return list;
}
复杂度分析：
时间复杂度：O(n + m) = O(n), 时间复杂度为两次遍历所用的时间
空间复杂度：O(n), map所需要的空间
-
测试用例
public static void main(String[] args) {
int[] nums = {4,1,-1,2,-1,2,3};
System.out.println(Arrays.toString(nums));
TopKFrequent topKFrequent = new TopKFrequent();
System.out.println("前 K 个高频元素:" + topKFrequent.topKFrequent(nums, 2));
}
-
结果
[4, 1, -1, 2, -1, 2, 3]
前 K 个高频元素:[-1, 2]
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
