| 题目链接 | 658. 找到 K 个最接近的元素 |
|---|---|
| 思路 | 二分+双指针 |
| 题解链接 | 官方题解 |
| 关键点 | 二分：查找到第一个>= val的位置；双指针：利用“有序”性质，双指针迭代跟踪left & right的位置 |
| 时间复杂度 | \(O(\log n + k)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
left, right = -1, len(arr)
while left + 1 < right:
mid = (left+right) // 2
if arr[mid] < x:
left = mid
else:
right = mid
left = right - 1
for _ in range(k):
if left < 0:
right += 1
elif right >= len(arr) or x - arr[left] <= arr[right] - x:
left -= 1
else:
right += 1
return arr[left+1:right]
Python-官方库
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
right = bisect_left(arr, x)
left = right - 1
for _ in range(k):
if left < 0:
right += 1
elif right >= len(arr) or x - arr[left] <= arr[right] - x:
left -= 1
else:
right += 1
return arr[left+1:right]