使用Java实现和应用小顶堆和大顶堆:力扣347题目前K个高频元素的解答
最编程
2023-12-31 14:53:13
...
java小顶堆、大顶堆实现和使用(例题:力扣347.前K个高频元素)
- java中堆的实现
- 小顶堆
- 大顶堆
- 堆使用的例题解析
- 力扣347.前K个高频元素
不对具体原理进行介绍,简单记录使用方式。
java中堆的实现
java中使用PriorityQueue类实现堆,构造函数一般可传入两个参数(size,new Comparator())
①size:初始化堆的大小,若不传则默认为11,并且堆的大小会根据实际情况,自动扩展
②new Comparator():定义了堆排序的比较方式。默认排序为小顶堆,若要实现大顶堆,则需要重写Comparator类的compare方法(见大顶堆);默认按自然排序,若要自定义排序方法,也需要重写此类(见力扣例题)
小顶堆
应用场景:寻找无序数组的前k个最大数
思想:遍历数组,用一个大小为k的小顶堆保存当前找到的前k个最大数,如果下一个数组元素比堆顶大,那堆顶元素必然不是前k大,将堆顶元素出堆,此数组元素入堆
public class run {
public static void main(String[] args) {
int[] nums = new int[]{1,5,4,2,3,6};
System.out.println(topKMax(nums, 5)); //输出:[2, 3, 4, 5, 6]
}
//寻找前k个最大的数--使用小顶堆
public static List<Integer> topKMax(int[] nums, int k){
//寻找前k个最小数,因此将小顶堆大小定义为k
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for(int i=0; i<nums.length; i++){
if(i<k){
pq.offer(nums[i]); //前k个数,直接入堆
}else if(nums[i]>pq.peek()){ //如果当前元素比堆顶元素大
pq.poll(); //说明堆顶元素(堆中最小元素)一定不属于前k大的数,出堆
pq.offer(nums[i]); //当前元素有可能属于前k大,入堆
}
}
List<Integer> ans = new ArrayList<>();
while(!pq.isEmpty()){
ans.add(pq.poll());
}
return ans;
}
}
大顶堆
注意:必须重写Comparator类的compare方法,在方法内用参数2减参数1(小顶堆为参数1减参数2)
应用场景:寻找无序数组的前k个最小数
思想:遍历数组,用一个大小为k的大顶堆保存当前找到的前k个最小数,如果下一个数组元素比堆顶小,那堆顶元素必然不是前k小,将堆顶元素出堆,此数组元素入堆
public class run {
public static void main(String[] args) {
int[] nums = new int[]{1,5,4,2,3,6};
System.out.println(topKMin(nums, 5)); //会从大到小输出:[5,4,3,2,1]
}
//寻找前k个最小的数--使用大顶堆
public static List<Integer> topKMin(int[] nums, int k){
//将大顶堆大小定义为k,并重写类函数
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b){
return b - a; //大顶堆:参数2-参数1;小顶堆:参数1-参数2
}
});
for(int i=0; i<nums.length; i++){
if(i<k){
pq.offer(nums[i]); //前k个数,直接入堆
}else if(nums[i]<pq.peek()){ //如果当前元素比堆顶元素小
pq.poll(); //说明堆顶元素(堆中最大元素)一定不属于前k小的数,出堆
pq.offer(nums[i]); //当前元素有可能属于前k小,入堆
}
}
List<Integer> ans = new ArrayList<>();
while(!pq.isEmpty()){
ans.add(pq.poll());
}
return ans;
}
}
堆使用的例题解析
力扣347.前K个高频元素
题目:给定一个非空的整数数组,返回其中出现频率前 k 高的元素
思路:“前k个最”是堆的一般使用场景,该题中的计量标准为频率,因此堆中比较的应该是元素频率。而堆中一般存的就是最终需要导进返回数组里的元素,因此需要重写PriorityQueue类中的比较函数,使得堆中存元素,但堆排序比较的是元素频率
public class Leetcode {
public static void main(String[] args) {
int[] nums = new int[]{4,1,-1,2,-1,2,3};
System.out.println(topKFrequent(nums,2)); //输出:[-1, 2]
}
public static List<Integer> topKFrequent(int[] nums, int k) {
//使用哈希存储元素与频率的映射
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
//使用小顶堆筛选前k个高频的元素,不能使用自然排序,需要重写比较的类函数
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
public int compare(Integer a, Integer b){
return map.get(a) - map.get(b); //堆中存放的是元素,但比较的应该是元素的频率
}
});
int size = 0;
for (Integer j : map.keySet()) {
if(size<k){
pq.offer(j); //前k个元素直接放入,自动排成小顶堆
size++;
}else if(map.get(j)>map.get(pq.peek())){
pq.poll();
pq.add(j);
}
}
//返回结果
List<Integer> ans = new ArrayList<>();
while(!pq.isEmpty()){
ans.add(pq.poll());
}
return ans;
}
}