我正在尝试解决以下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
元素。如何实现比较器功能,以这种方式对元素进行排序?
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());
}
执行Collections.sort(ints);
并返回结果。
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;
});