658. 找到 K 个最接近的元素
class FindClosestElements:
"""
658. 找到 K 个最接近的元素
https://leetcode.cn/problems/find-k-closest-elements/description/
"""
def solution(self, arr: List[int], k: int, x: int) -> List[int]:
p = self.left_bound(arr, x)
res = []
l, r = p - 1, p
while r - l - 1 < k:
if l == -1:
res.append(arr[r])
r += 1
elif r == len(arr):
res.insert(0, arr[l])
l -= 1
elif x - arr[l] > arr[r] - x:
res.append(arr[r])
r += 1
else:
res.insert(0, arr[l])
l -= 1
return res
def left_bound(self, arr: List[int], x: int) -> int:
l, r = 0, len(arr)
while l < r:
mid = l + (r - l) // 2
if arr[mid] >= x:
r = mid
else:
l = mid + 1
return l