找到K个最接近的元素（LeetCode）

题目

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

• |a - x| < |b - x| 或者
• |a - x| == |b - x| 且 a < b

解题

"""
时间复杂度为 O(log(n-k) + k)，其中 n 是数组的长度。二分查找部分的时间复杂度为 O(log(n-k))，而结果提取部分的时间复杂度为 O(k)
"""from typing import Listdef findClosestElements(arr, k, x):# 二分查找，找到最接近 x 的元素的位置left, right = 0, len(arr) - k# 使用二分查找来确定最左边的边界while left < right:mid = (left + right) // 2# 比较 x 与 arr[mid] 和 arr[mid + k] 的距离if x - arr[mid] > arr[mid + k] - x:left = mid + 1else:right = mid# 从找到的 left 位置开始的 k 个元素即为结果return arr[left:left + k]# 示例输入
arr = [1, 2, 3, 4, 5]
k = 4
x = 3
result = findClosestElements(arr, k, x)
print(result)  # 输出: [1, 2, 3, 4]