堆(heap)是一种特殊的数据结构,它通常被看作是一棵树的数组对象,堆总是一颗完全二叉树。
堆分为最大堆和最小堆,在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。
堆经常使用的场景:
- 构建优先队列
- 堆排序
- 快速找出一个集合中的前N大(小)的值
问题概述:给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
解题思路:相当与找出一个集合中前 k 大的值。
Java语言中的优先队列 PriorityQueue 就是使用堆实现的,我们可以使用优先队列解决本题。
Java代码:
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> numMap = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
numMap.put(nums[i], numMap.getOrDefault(nums[i], 0) + 1);
}
// 优先队列,自定义排序方式
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
for(Map.Entry<Integer, Integer> entry : numMap.entrySet()) {
if(queue.size() < k) {
queue.offer(new int[] {entry.getKey(), entry.getValue()});
} else {
int min = queue.peek()[1];
if(min < entry.getValue()) {
queue.poll();
queue.offer(new int[] {entry.getKey(), entry.getValue()});
}
}
}
int[] result = new int[k];
for(int i = 0; i < k; i++) {
result[i] = queue.poll()[0];
}
return result;
}
}
问题概述:给一非空的单词列表,返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
解题思路:和上题类似,只是排序方式发生了变化。
Java代码:
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> frequentMap = new HashMap<String, Integer>();
for(int i = 0; i < words.length; i++) {
frequentMap.put(words[i], frequentMap.getOrDefault(words[i], 0) + 1);
}
PriorityQueue<String> queue = new PriorityQueue<String>(
new Comparator<String>() {
@Override
public int compare(String a1, String a2) {
int b = frequentMap.get(a1) - frequentMap.get(a2);
if(b != 0) {
return b;
} else {
return -a1.compareTo(a2);
}
}
}
);
for(Map.Entry<String, Integer> entry : frequentMap.entrySet()) {
queue.offer(entry.getKey());
if(queue.size() > k) {
queue.poll();
}
}
List<String> result = new ArrayList<String>();
while(!queue.isEmpty()) {
result.add(queue.poll());
}
Collections.reverse(result);
网友评论