java - Priority Queue未根据Java中的优先级返回正确的值

我有一个数组，我必须从该数组中获取最高的k个频繁整数。

int[] nums = new int[] {5,3,1,1,1,3,73,1};
int k  = 2

我的功能如下所示：

static public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    if (nums.length == 0)
        return res;
    Map<Integer, Integer> hash = new HashMap<>();
    for (int i : nums) {
        hash.put(i, hash.getOrDefault(i, 0) + 1);
    }

    System.out.println(hash);

    Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
            (a, b) -> a.getValue() > b.getValue()? a.getValue():b.getValue()
    );
    for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
        pq.offer(entry);
    }

    System.out.println(pq);

    System.out.println(pq.poll());
    System.out.println(pq.poll());

//  for (int i=0; i<k; i++)
//      res.add(pq.poll().getKey());

    return res;
}

但是，当我从优先级队列中打印前2个元素时，我得到：
输出：

{1=4, 3=2, 5=1, 73=1} // hash map output
[1=4, 3=2, 5=1, 73=1] // complete priority queue output
1=4 // first poll from priority queue
5=1 // second poll from priority queue

第二项返回错误，应该是3=2。
谁能告诉我代码有什么问题吗？比较器不正确吗？

最佳答案

问题出在您的比较器的比较方法上。比较方法合同为


如果a小于b，则返回负整数。
如果大于b，则返回正整数。
如果a等于b，则返回0。


尝试下面的代码

static public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    if (nums.length == 0)
        return res;
    Map<Integer, Integer> hash = new HashMap<>();
    for (int i : nums) {
        hash.put(i, hash.getOrDefault(i, 0) + 1);
    }

    System.out.println(hash);


    Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
            (a, b) -> Integer.compare(b.getValue(), a.getValue())
    );
    for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
        pq.offer(entry);
    }


    for (int i = 0; i < k; i++) {
        res.add(pq.poll().getKey());
    }
    return res;
}