原题
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
- 如果 A = [1, 2, 3], target = 2 and k = 3, 那么返回 [2, 1, 3]
- 如果 A = [1, 4, 6, 8], target = 3 and k = 3, 那么返回 [4, 1, 6]
解题思路
- 使用Binary Search找到最接近的数字的位置
- 双指针从该位置左右移动，每次比较找到最接近的数字，加入到答案中，相应的指针++
- 中间while循环可以略作简化，通过优先处理特殊情况
while k > 0:
if left < 0:
res.append(A[right])
right += 1
k -= 1
elif right > len(A) - 1:
res.append(A[left])
left -= 1
k -= 1
else:
if abs(A[left] - target) <= abs(A[right] - target):
res.append(A[left])
left -= 1
k -= 1
else:
res.append(A[right])
right += 1
k -= 1
完整代码
class Solution:
# @param {int[]} A an integer array
# @param {int} target an integer
# @param {int} k a non-negative integer
# @return {int[]} an integer array
def kClosestNumbers(self, A, target, k):
# Write your code here
if not A or k == 0:
return []
res = []
index = self.binarySearch(A, target)
res.append(A[index])
k -= 1
left, right = index - 1, index + 1
while k > 0:
if left >= 0 and right <= len(A) - 1:
if abs(A[left] - target) <= abs(A[right] - target):
res.append(A[left])
left -= 1
k -= 1
else:
res.append(A[right])
right += 1
k -= 1
if left < 0:
while k > 0 and right <= len(A) - 1:
res.append(A[right])
right += 1
k -= 1
break
if right > len(A) - 1:
while k > 0 and left >= 0:
res.append(A[left])
left -= 1
k -= 1
break
return res
def binarySearch(self, L, target):
start, end = 0, len(L) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if L[mid] == target:
return mid
elif L[mid] > target:
end = mid
else:
start = mid
return start if abs(L[start] - target) <= abs(L[end] - target) else end
