二分+双指针,时间复杂度:O(logn + k) ,空间复杂度O(k) 。
由于给定一个升序排序的数组,故可以用二分找到最接近x的元素。
用二分找到等于x的元素或大于x的最小元素a[l] ,而大于x的最小元素可能不是最接近x的元素,故还需要和小于x的最大元素比较哪个更接近x,若小于x的更接近,则--l。
由于序列为升序,故在最接近x的元素a[l] 前后找k - 1个比较接近x的元素即可。
最后,[i, j] 即为最接近x的k个元素。
不论是负数和负数、负数和正数还是正数和正数,较大的数减去较小的数一定是两数之差的绝对值,即两数的距离。
class Solution {
class Node {
int a, b;
public Node() {}
public Node(int a, int b) {
this.a = a;
this.b = b;
}
}
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.length - 1, mid;
while (l < r) {
mid = l + r >> 1;
if (arr[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
Node a, b;
if (l > 0 && arr[l] != x) {
a = new Node(x - arr[l - 1], arr[l - 1]);
b = new Node(arr[l] - x, arr[l]);
if (compare(a, b)) {
--l;
}
}
int i = l, j = i;
for (int p = 1; p < k; ++p) {
if (i - 1 < 0) {
++j;
} else if (j + 1 == arr.length) {
--i;
} else {
a = new Node(x - arr[i - 1], arr[i - 1]);
b = new Node(arr[j + 1] - x, arr[j + 1]);
if (compare(a, b)) {
--i;
} else {
++j;
}
}
}
List<Integer> res = new ArrayList<>();
for (int p = i; p <= j; ++p) {
res.add(arr[p]);
}
return res;
}
boolean compare(Node o1, Node o2) {
return o1.a == o2.a ? o1.b < o2.b : o1.a < o2.a;
}
}
堆+排序,时间复杂度:O(nlogk) ,空间复杂度O(k) 。
维护k个元素最接近x的大根堆,堆顶元素为大根堆中最接近x的最大元素。
当堆中的元素数量大于k时,弹出堆顶元素,即堆中还剩下k个最接近x的元素。
class Solution {
class Node {
int a, b;
public Node() {}
public Node(int a, int b) {
this.a = a;
this.b = b;
}
}
public List<Integer> findClosestElements(int[] arr, int k, int x) {
Queue<Node> pq = new PriorityQueue<>((o1, o2) -> o2.a == o1.a ? o2.b - o1.b : o2.a - o1.a);
for (int i = 0; i < arr.length; ++i) {
pq.add(new Node(Math.abs(arr[i] - x), arr[i]));
if (pq.size() > k) {
pq.poll();
}
}
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.poll().b);
}
Collections.sort(res);
return res;
}
}