LeetCode——队列

发布时间:2024年01月07日

队列

主要是优先队列的例题,以及优先队列如何使用(堆的性质,队列的存取)

优先队列:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.peek();  // 获取堆顶元素
minHeap.offer(num);  // 入堆
minHeap.poll();  // 弹出

本质:完全二叉树
1.数组中的第K个最大元素

// class Solution {
//     public int findKthLargest(int[] nums, int k) {
//         // 思路一:暴力解法,JDK默认使用快速排序
//         int len = nums.length;
//         Arrays.sort(nums);
//         return nums[len - k];
//     }
// }

// 优先队列
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 思路二:构造一个含有k个元素的小顶堆,先拿k个元素初始化堆,接着继续遍历,判断是否要将此元素再放入堆中,最后从堆顶也就是队头拿出来的元素就是第k大的元素
        int len = nums.length;
        // 定义含k个元素的小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < len; i++) {
            if (i < k) {
                minHeap.offer(nums[i]);  // 入堆
            } else {
                if(nums[i] > minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(nums[i]);
                }
            }
        }
        return minHeap.peek();
    }
}

2.前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 思路:定义一个HashMap,统计每个整数出现的频次;将频次作为入堆的依据
        HashMap<Integer, Integer> map = new HashMap<>();
        // 1. 统计每个数字出现的频次
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // map.get(nums[i]) ++;
            // map.getOrDefault()如果键存在就获取键对应的值,如果不存在就使用默认值0
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // 2. 试着将map作为优先队列的元素
        // 存的时map的key,但是想要根据map的value值维护小顶堆!!!!
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return map.get(a) - map.get(b);
            }
        });
        map.forEach((key, val) -> {
            if (minHeap.size() < k) {
                minHeap.offer(key);
                // System.out.println("初始化时插入的"+ key);
            } else {
                if(val > map.get(minHeap.peek())) {
                    minHeap.poll();
                    minHeap.offer(key);
                    System.out.println(key);
                }
            }

            System.out.println(key + "--->" + val);
        });
        // 3. 定义接收数组
        int[] res = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            res[index] = minHeap.poll();
            index ++;
        }
        return res;
    }
}

3.数据流的中位数

class MedianFinder {
    // 定义一个小顶堆,一个大顶堆
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;

    public MedianFinder() {
        // 重写Comparator方法,默认构造出来的是小顶堆,
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
    }
    
    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }
    
    public double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}

搞清楚现在里面存的是什么值,PriorityQueue会自动进行排序,自己实现PriorityQueue的关键是完全二叉树的调整,如果是小顶堆,插入元素,放在最后一个结点,不断比较与双亲结点的值大小,向上调整

[未完待续……]

文章来源:https://blog.csdn.net/qq_44689664/article/details/135438474
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。