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

lmyy7pcs  于 2023-02-07  发布在  Java
关注(0)|答案(4)|浏览(184)

我正在尝试解决以下leetcode问题:
给定一个排序数组,两个整数k和x,找出数组中最接近x的k个元素。结果也应该按升序排序。如果有平局,总是优先选择较小的元素。
示例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元素,我如何实现一个比较器函数,以这种方式对元素进行排序?

qltillow

qltillow1#

我会利用默认的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());
}
kpbwa7wx

kpbwa7wx2#

这里,问题不在于你的优先级队列,而是我们需要两个不同排序格式的结果.你的队列将给予前K个元素,但这将永远不会是升序,因为它排序元素相对于距离“X”,所以对于给定的X=4,元素3和5都在同一级别,所以你的结果将有类似[4,3,5]的数据.
最好对结果列表进行单独排序。
执行Collections.sort(ints);并返回结果。

bvjveswy

bvjveswy3#

在您的实现中,您没有检查两个整数到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;
                });
ryevplcw

ryevplcw4#

Queue<Integer> pq = new PriorityQueue<>((a,b)->(Math.abs(a-x)<Math.abs(b-x))?1:-1);

相关问题