priorityqueue算法搜索最小k值返回错误结果

monwx1rj  于 2021-07-03  发布在  Java
关注(0)|答案(1)|浏览(288)

我试图找到数组的最小第k个值。我使用priorityqueue数据结构来删除大于k的值,但返回的结果不正确。我的代码如下:

public class Main2 {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();

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

        for(int num : arr) {
            maxHeap.add(num);
            if(maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return maxHeap.peek(); 
    }

    public static void main(String[] args) {
        int arr[] = { 12, 3, 5, 7, 4, 19, 26 };

        Main2 smallest = new Main2();
        int result = smallest.smallestK(arr, 3); //should return 5, but returns 12
        System.out.println(result);
    }
}

如何修正算法以返回正确的结果?

ecfsfe2w

ecfsfe2w1#

您没有创建最大堆,而是创建最小堆。要创建最大堆,需要将比较器传递给priorityqueue构造函数:

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

相关问题