为我的 PriorityQueue 实现自定义比较器

Question

我正在尝试解决以下 leetcode 问题：

给定一个排序数组，两个整数 k 和 x，找到数组中 k 个最接近 x 的元素。结果也应该按升序排序。如果有平局，则始终首选较小的元素。

示例 1：输入：[1,2,3,4,5], k=4, x=3

输出：[1,2,3,4]

示例 2：输入：[1,2,3,4,5], k=4, x=-1

输出：[1,2,3,4]

我目前不正确的解决方案如下：

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));

       for(int i=0; i<arr.length; i++) {
           pq.add(arr[i]);

       }



        ArrayList ints = new ArrayList<>();

        for(int i=0;i<k;i++) {
            ints.add(pq.poll());


        }
        return ints;
    }
}

问题出在我传递给构造函数的比较器上。这个想法是我希望我的比较器根据任何整数 i 和输入 x 之间的最小距离对整数进行排序，然后从队列中轮询 k 元素。我怎样才能实现以这种方式对元素进行排序的比较器函数？

Answer 1

在您的实现中，您没有检查两个整数与 X 的距离相同的情况。
以下比较器实现将给出正确的结果：

PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, 
                (a,b) -> {
                    int comp = Integer.compare(Math.abs(a - x), Math.abs(b - x));
                    if(comp==0) {return Integer.compare(a, b);}
                    return comp;
                });

Answer 2

在这里，问题不在于您的优先级队列，而是我们需要两个具有不同排序格式的结果。您的队列将给出前 K 个元素，但它永远不会按升序排列，因为它根据距 "X" 的距离对元素进行排序，因此对于给定的 X=4，元素 3 和 5 都处于同一级别，因此您的结果会有类似 [4,3,5].

的数据

最好对结果列表进行单独排序。

执行Collections.sort(ints);并return结果。

Answer 3

我会利用默认的 Integer.compare 方法。基本上你想要的是首先检查绝对差异的比较，如果是平局则进行正常比较。

static int compare(int x, int a, int b) {
    int comp = Integer.compare(Math.abs(a - x), Math.abs(b - x));
    if (comp == 0) {
        return Integer.compare(a, b);
    }
    return comp;
}

这使得编写实际的优先级队列实现变得非常干净

static List<Integer> findClosestElements(int[] arr, int k, int x) {
    PriorityQueue<Integer> queue = new PriorityQueue<>(
        arr.length, (a,b) -> compare(x, a, b));
    Arrays.stream(arr).forEach(queue::add);
    return queue.stream().limit(k).sorted().collect(Collectors.toList());
}

为我的 PriorityQueue 实现自定义比较器

Implement a custom comparator for my PriorityQueue

java

heap

priority-queue

comparator