优先级队列未根据Java中的优先级返回适当的值

Question

我有一个数组，我必须从该数组中获取最高的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。谁能告诉我代码有什么问题吗？比较器不正确吗？

Answer 1

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

1. 如果a小于b，则返回负整数。
2. 如果大于b，则返回正整数。
3. 如果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;
}

Answer 2

您定义的Comparator错误。它永远不会返回负数。从Comparator文档中，Comparator.compare方法应返回：

负数，零或正整数，因为第一个参数小于，等于或大于第二个参数。

[而不是滚动自己的比较器-您可以使用静态Comparator.compare方法（如果至少使用Java 8，则可以：）：

compare

或

Comparator