29栈与队列——优先队列

目录

LeetCode之路——347. 前 K 个高频元素

分析

优先队列

简单示例

运行结果

源码简析

---

LeetCode之路——347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105

• k 的取值范围是 [1, 数组中不相同的元素的个数]

• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

分析

1.需要统计各个元素的频率，用Map，元素为key，频率为value。

2.通过map排序(从大到小)选出k个元素。

3.推荐优先队列

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 优先队列默认排序：小的在队首queue[0]=min
        PriorityQueue pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map map = new HashMap<>(); // 记录元素出现次数
        for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        for(int i = 0; i < k; i ++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }
}
​

• 时间复杂度：O(n logk)

• 空间复杂度：O(n)

优先队列

优先级队列（PriorityQueue）是一种特殊类型的队列，它根据元素的优先级进行排序，使得可以以优先级最高的元素首先出队。优先级队列通常用最小堆（Min-Heap）数据结构实现，但也可以用最大堆（Max-Heap）来实现，具体取决于所需的排序顺序。

Java中优先级队列的主要特点和用法：

1. 元素排序： 优先级队列中的元素根据其优先级进行排序，通常具有特定的比较规则或者通过元素的自然顺序来排序。

2. 最小堆和最大堆： 默认情况下，Java的优先级队列是最小堆，即具有最小优先级的元素首先出队。可以通过提供自定义比较器来实现最大堆，以便具有最大优先级的元素首先出队。

3. 插入和删除： 优先级队列支持插入和删除元素的操作，插入操作通常称为offer()或add()，删除操作通常称为poll()。

4. 获取元素： 优先级队列允许查看队列中的优先级最高的元素而不移除它，这通常使用peek()方法。

5. 元素不重复： 默认情况下，Java中的优先级队列不允许重复元素，每个元素在队列中只出现一次。如果需要允许重复元素，可以自行实现。

简单示例

此示例创建了一个最小堆的优先级队列，插入一些元素，并演示了如何查看和删除队列中的元素：

public class PriorityQueueExample{
    public static void main(String[] args) {
        // 创建一个最小堆的优先级队列
        PriorityQueue minHeap = new PriorityQueue<>();
​
        for (int i = 0; i < 5; i++) {
            int num =new Random().nextInt(100);
            System.out.println("随机数："+ num);
            minHeap.offer(num); 
            // 查看队列中的最小元素
            int minElement = minHeap.peek();
            System.out.println("最小元素: " + minElement);
        }
​
        // 删除队列中的最小元素
        int removedElement = minHeap.poll();
        System.out.println("删除的元素: " + removedElement);
    }
}

运行结果

源码简析

offer(E e)默认实现了最小堆的排序。也就是queue[0]=min的效果

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
​
    // 在位置k插入x，通过比较将x放到最顶端
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }