优先级队列未根据 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

你定义的Comparator是错误的。它永远不会 return 是负数。从 Comparator.compare 文档中，compare 方法应该 return :

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

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

Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
        Comparator.comparing(Map.Entry::getValue, Comparator.reverseOrder())
);

或

Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
        (e1, e2) -> - Integer.compare(e1.getValue(), e2.getValue())
);

Answer 2

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

如果 a 小于 b return 负整数。
如果a大于breturn正整数。
如果 a 等于 b 那么 return 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;
}

优先级队列未根据 Java 中的优先级返回正确的值

Priority Queue is not returning proper value according to priority in Java

java

priority-queue

comparator