共计 1660 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 658. 找到 K 个最靠近的元素 ，难度为 中等。
Tag :「二分」、「双指针」
给定一个 排序好 的数组 arr，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的后果必须要是按升序排好的。
整数 a 比整数 b 更靠近 x 须要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
示例 1：
输出：arr = [1,2,3,4,5], k = 4, x = 3
输入：[1,2,3,4]示例 2：
输出：arr = [1,2,3,4,5], k = 4, x = -1
输入：[1,2,3,4]提醒：
- $1 <= k <= arr.length$
- $1 <= arr.length <= 10^4$
arr按升序排列- $-10^4 <= arr[i], x <= 10^4$
二分 + 双指针
容易想到先通过「二分」找到与 x 差值最小的地位 idx，而后从 idx 开始应用「双指针」往两边进行拓展（初始化左端点 $i = idx – 1$，右端点 $j = idx + 1$），含意为 $[i + 1, j – 1]$ 范畴内子数组为候选区间，一直依据两边界与 x 的差值关系进行裁减，直到候选区间蕴含 $k$ 个数。
Java 代码：
class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {
int n = arr.length, l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid] <= x) l = mid;
else r = mid - 1;
}
r = r + 1 < n && Math.abs(arr[r + 1] - x) < Math.abs(arr[r] - x) ? r + 1 : r;
int i = r - 1, j = r + 1;
while (j - i - 1 < k) {if (i >= 0 && j < n) {if (Math.abs(arr[j] - x) < Math.abs(arr[i] - x)) j++;
else i--;
} else if (i >= 0) {i--;} else {j++;}
}
List<Integer> ans = new ArrayList<>();
for (int p = i + 1; p <= j - 1; p++) ans.add(arr[p]);
return ans;
}
}TypeScript 代码：
function findClosestElements(arr: number[], k: number, x: number): number[] {
let n = arr.length, l = 0, r = n - 1
while (l < r) {
const mid = l + r + 1 >> 1
if (arr[mid] <= x) l = mid
else r = mid - 1
}
r = r + 1 < n && Math.abs(arr[r + 1] - x) < Math.abs(arr[r] - x) ? r + 1 : r
let i = r - 1, j = r + 1
while (j - i - 1 < k) {if (i >= 0 && j < n) {if (Math.abs(arr[j] - x) < Math.abs(arr[i] - x)) j++
else i--
} else if (i >= 0) {i--} else {j++}
}
return arr.slice(i + 1, j);
};- 工夫复杂度：查找宰割点复杂度为 $O(\log{n})$；从宰割点往两边拓展复杂度为 $O(k)$。整体复杂度为 $O(\log{n} + k)$
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.658 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
正文完
