0658-find-k-closest-elements.adoc

658. 找到 K 个最接近的元素

LeetCode - 658. 找到 K 个最接近的元素

给定一个 排序好 的数组 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,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

提示：

• 1 <= k <= arr.length

• 1 <= arr.length <= 104

• arr 按 升序 排列

• -104 <= arr[i], x <= 104

思路分析

二分查找或双指针或排序。可以通过二分查找，找到边界，然后向两边扩充。也可以直接按照接近因子算法，进行直接排序。

一刷

link:{sourcedir}/_0658_FindKClosestElements.java[role=include]

参考资料

1. 658. 找到 K 个最接近的元素 - 官方题解

2. 658. 找到 K 个最接近的元素 - 排除法（双指针）+ 二分法（Java、Python）