在排序数组中找最接近的K个数

https://www.lintcode.com/problem/460/

给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。

1. k是一个非负整数，并且不大于已排序数组的长度。

2. 给定数组的长度是正整数, 不会超过 $104104$

3. 数组中元素的绝对值不会超过 $104104$

样例

样例 1:

输入: A = [1, 2, 3], target = 2, k = 3输出: [2, 1, 3]

样例 2:

输入: A = [1, 4, 6, 8], target = 3, k = 3输出: [4, 1, 6]

挑战

O(logn + k) 的时间复杂度

解题思路：利用二分找出第一个>= target的数，以此为index分别向左右查找最接近target的数。 注意此刻先考虑边界，如果左边触头，则将剩下右边元素都加入，反之亦然。

from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @param target: An integer
    @param k: An integer
    @return: an integer array
    """
    def k_closest_numbers(self, a: List[int], target: int, k: int) -> List[int]:
        # write your code here
        
        if not a:
            return []
        l,r = 0, len(a)-1
        while l + 1 < r:
            mid = (l+r) // 2
            if a[mid] < target :
                l = mid
            else:
                r = mid
        res = []
        i, j = l, l + 1
        
        #利用m来循环K次，而不是用while+k--，减少错误
        for m in range(k):
            if i < 0:
                res.append(a[j])
                j += 1
            elif j >= len(a):
                res.append(a[i])
                i -= 1
            else:
                if target - a[i] <= a[j] - target:
                    res.append(a[i])
                    i -= 1
                else:
                    res.append(a[j])
                    j += 1
        
        return res