658. 找到 K 个最接近的元素 Medium
给定一个 排序好 的数组 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]
解题思路
输入：一个排好序的数组 arr, 两个整数 k 和 x
输出：找出最接近 x 的 k 个数，并且要排好序返回
本题是典型的 相向双指针 问题。
我们可以想象一下在坐标轴中，离某一个值越远就意味着差值绝对值越大，所以本题可以看成是在坐标轴中找离 x 最近的 k 个数，或者说 k 长的窗口，这些数是要在 arr 数组里出现的
我们可以定义两个指针 left = 0 和 right = len(arr) - 1
- 当
right - left >= k的时候就意味着还需要缩小窗口 - 那这时候判断两边哪个离 x 更近
- 如果
abs(arr[left]) - x > abs(arr[right] - x)则要丢弃左边的数字，因为右边的数字更靠近 x - 反之则丢弃右边的
最后我们会得到一个 k 大的窗口 [l, r]，返回 arr[l: r + 1] 就是我们要的答案
代码实现
python
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n = len(arr)
left, right = 0, n - 1 # 初始化双指针，指向数组两端
# 保证窗口大小最终为 k
while right - left >= k:
# 比较左右两端哪个离 x 更远，舍弃较远的一侧
if abs(arr[left] - x) > abs(arr[right] - x):
left += 1 # 左边更远，左指针右移
else:
right -= 1 # 右边更远或一样远，右指针左移
# 返回最终窗口内的 k 个元素
return arr[left:right + 1]javascript
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
const findClosestElements = function(arr, k, x) {
let left = 0;
let right = arr.length - 1;
while (right - left >= k) {
if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
left++;
} else {
right--;
}
}
return arr.slice(left, right + 1);
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)