高效算法中的优先队列甄选

文章标题：

优先队列在算法问题中的巧妙应用

目录

• 一、1046.最后的石头重量计算
• 二、703. 数据流里的第 K 大元素
• 三、692. 前 K 个高频词语
• 四、295. 数据流的中位数求解

一、1046.最后的石头重量计算

题目链接：1046.最后的石头重量
题目描述：
![

](https://i-blog.csdnimg.cn/direct/16f199517b0d47498355823b0f1d8334.png)

题目解析：

• 该问题要求我们从给定的数组中不断取出最大的两个元素，让它们相减后将差值重新放入数组，重复此过程直到数组为空或只剩一个元素。

解题思路：

• 直接对数组排序会频繁操作，效率不高。此时可使用优先队列（大根堆），能快速取出最大元素，降低操作开销。

解题代码：

//时间复杂度 O(n)
//空间复杂度 O(n)
class Solution {
    public int lastStoneWeight(int[] stones) {
        //创建大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(
            (a,b) -> b - a
        );
        //将数组元素加入堆中
        for(int i = 0; i < stones.length; i++)
            queue.offer(stones[i]);
        //循环处理，直到堆中只剩一个或没有元素
        while(!queue.isEmpty() && queue.size() != 1) {
            int y = queue.poll();
            int x = queue.poll();
            queue.offer(y-x); 
        }
        //返回结果，如果堆为空返回0，否则返回剩余元素
        return queue.isEmpty() ? 0 : queue.poll();
    }
}

二、703. 数据流里的第 K 大元素

题目链接：703. 数据流中的第 K 大元素

题目描述：
![

](https://i-blog.csdnimg.cn/direct/7b82ee541d5a4890b4ebe3b6e3473fea.png)

题目解析：

• 给定一个数组和整数K，需通过类的add方法，每次添加元素后返回当前数组中第K大的元素。

解题思路：

• 利用大小为K的小根堆，堆中始终保存当前数组中第K大到最大的元素，堆顶即为第K大元素。

解题代码：

//时间复杂度 O(nLogK)
//空间复杂度 O(K)
class KthLargest {
    PriorityQueue<Integer> heap;
    int kValue;

    public KthLargest(int k, int[] nums) {
        heap = new PriorityQueue<Integer>();
        kValue = k;
        for(int i = 0; i < nums.length; i++) {
            heap.offer(nums[i]);
            if(heap.size() > kValue) {
                heap.poll();
            }
        }

    }

    public int add(int val) {
        heap.offer(val);
        if(heap.size() > kValue) {
            heap.poll();
        }
        return heap.peek();
    }
}

三、692. 前 K 个高频词语

题目链接：692. 前 K 个⾼频单词

题目描述：
![

](https://i-blog.csdnimg.cn/direct/9867706b13004912a11605b9a5555c3b.png)

题目解析：

• 给定字符串数组words，需找出出现频率最高的前K个字符串，频率相同时按字典序从小到大排列。

解题思路：

• 先用哈希表统计字符串出现次数，再用大小为K的堆，结合自定义比较器处理频率和字典序，最后逆序结果得到正确顺序。

解题代码：

//时间复杂度：O(NLogK)
//空间复杂度：O(N)
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> countMap = new HashMap<>();

        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
            (a,b) -> {
            //频率相同时按字典序降序，保证弹出时为升序
            if(a.getValue().equals(b.getValue())) {
                return b.getKey().compareTo(a.getKey());
            }
            //频率不同时按升序
            return a.getValue() - b.getValue();
        });
        //统计单词出现次数
        for( String s : words) {
            countMap.put(s, countMap.getOrDefault(s ,0) + 1);
        }
        //将元素放入堆，保持堆大小不超k
        for(Map.Entry<String, Integer> entry : countMap.entrySet()) {
            heap.offer(new Pair<>(entry.getKey(),entry.getValue()));
            if(heap.size() > k) {
                heap.poll();
            }
        }
        //收集结果并逆序
        List<String> result = new ArrayList<String>();
        while(!heap.isEmpty()) {
            result.add(heap.poll().getKey());
        }
        Collections.reverse(result);
        return result;
    } 
}

四、295. 数据流的中位数求解

题目链接：295. 数据流的中位数

题目描述：

• 需实现一个类，能初始化、添加元素，并在添加后快速获取数据流的中位数。

题目解析：

• 通过维护大根堆和小根堆，根据元素个数调整堆的分布，从而快速得到中位数。

解题思路：

• 维护大根堆（存前半部分元素）和小根堆（存后半部分元素），根据插入元素的大小和堆的情况调整元素分布，保证元素个数为偶数时两堆平衡，奇数时一堆多一个元素。

解题代码：

//时间复杂度：O(LogN)
//空间复杂度：O(N)
class MedianFinder {
    //记录元素个数
    int elementCount = 0;
    //大根堆存储前半部分元素
    PriorityQueue<Integer> maxHeap;
    //小根堆存储后半部分元素
    PriorityQueue<Integer> minHeap;


    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a,b) ->{
            return b - a;
        });
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        elementCount++;
        if(elementCount == 1 ) {
            maxHeap.offer(num);
            return;
        }
        //元素个数为偶数且当前数大于大根堆堆顶
        if(elementCount % 2 == 0 && maxHeap.peek() <= num) {
            if(maxHeap.size() < minHeap.size()) {
                if(!minHeap.isEmpty() && minHeap.peek() >= num) {
                    maxHeap.offer(num);
                }else {
                    int temp = minHeap.poll();
                    maxHeap.offer(temp);
                    minHeap.offer(num);
                }
            }else {
                minHeap.offer(num);
            }
            return;
        } 
         //元素个数为偶数且当前数小于大根堆堆顶
        if(elementCount % 2 == 0 && maxHeap.peek() > num) {
            if(maxHeap.size() < minHeap.size()) {
                maxHeap.offer(num);
            }else {
                int temp = maxHeap.poll();
                maxHeap.offer(num);
                minHeap.offer(temp);

            }
            return;
        } 
         //元素个数为奇数且当前数小于大根堆堆顶
         if(elementCount % 2 != 0 && maxHeap.peek() >= num) {
            maxHeap.offer(num);
         } else {
            minHeap.offer(num);
         }
    }

    public double findMedian() {
        if(elementCount % 2 == 0) {
                return (double)((maxHeap.peek() + minHeap.peek())/ 2.0);
        }
        if(maxHeap.size() > minHeap.size()) {
             return maxHeap.peek();
        } else {
            return minHeap.peek();
        }

    }
}