selectK这样的实现方式出错在哪里呢

public int findKthLargest(int[] arr, int k) {

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < k; i++) {
        pq.enqueue(arr[i]);
    }
    for (int i = k; i <arr.length ; i++) {
        if (!pq.isEmpty()&&arr[i] > pq.getFront()) {
            pq.dequeue();
            pq.enqueue(arr[i]);
        }
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = pq.dequeue();
    }
    return res[k];
}

warren_au 2020-10-15

源自：堆，优先队列和堆排序 2-4 使用优先队列的思想解决 Leetcode 215

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2020-10-15 19:08:06

我不确定你的代码是否还有别的问题，但最基本的，res 的大小只有 k，其索引是 0 到 k - 1，res[k] 数组越界。

请仔细调试你的代码，用小数据量单步跟踪测试，看看你的程序每一步执行后，每一个变量在怎么变化，和你的思考是否一样？如果不一样，自己的思考哪里错了？切记：正确的程序和对程序更深刻的理解是调试出来的，不是看出来的。进步就再这个过程中。

加油！：）

收起回答

warren_au 提问者 #1

针对这段代码，假设使用最小堆实现的优先队列pq pq每次出队的都是最小值赋给res[i] 最后我想给出整个数组中最大值应该是res[k-1],因为每次出队的都是最小值，以此类推，所以return res[k-1];来获取最大值，是这个思路，请问哪里有问题吗？ int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = pq.dequeue(); } return res[k-1];

2020-10-15 19:29:58
liuyubobobo 回复提问者 warren_au #2

pq 是最小堆，pq 里存的是最大的 k 个数，第 k 大的数应该是 res[0]。

2020-10-16 02:38:39
warren_au 提问者 #3

我使用最小堆实现的队列是这样的 private MinHeap<E> minHeap; public PriorityQueue() { minHeap = new MinHeap<>(); } @Override public int getSize() { return minHeap.size(); } @Override public boolean isEmpty() { return minHeap.isEmpty(); } @Override public void enqueue(E e) { minHeap.add(e); } @Override public E dequeue() { return minHeap.extractMin(); } @Override public E getFront() { return minHeap.findMin(); } } 所以出队的是最小值啊，pq 里存的是最大的 k 个数，第 k 大的数应该是 res[k-1]？

2020-10-17 13:59:21