Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or|a - x| == |b - x|anda < b
Solution
先用二分确定 x 的位置，然后用双指针来确定左右范围
点击查看代码
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
def left_bound(arr, x):
left = 0
right = len(arr)
while left<right:
mid = left+int((right-left)/2)
if arr[mid]==x:
right=mid
elif arr[mid]<x:
left=mid+1
elif arr[mid]>x:
right=mid
return left
right = left_bound(arr,x)
left = right-1
print(right, left)
for _ in range(k):
if left<0:
right+=1
elif right>=len(arr):
left-=1
else:
if x-arr[left]<=arr[right]-x:
left-=1
else:
right+=1
return arr[left+1:right]