题目描述
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
k是一个非负整数，并且总是小于已排序数组的长度；
给定数组的长度是正整数, 不会超过 10^4；
数组中元素的绝对值不会超过 10^4
测试样例
输入: A = [1, 2, 3], target = 2, k = 3
输出: [2, 1, 3]
输入: A = [1, 4, 6, 8], target = 3, k = 3
输出: [4, 1, 6]
思路
由于数组是已排序的，自然容易想到用二分查找找出目标在数组中应插入的位置。然后由这个位置开始向两边进行遍历，计算左右两边的数与目标的差值，取差值小的，直至取满k个数。注意，由于接近程度相同时，小的数需要排在前面，因此要先对左边的数进行计算。
最后，若左右其中一个方向取到了底，而此时仍未取够k个数，则从另一还有数字可取的方向取满至k个数。
代码
# 为了方便，可以直接使用该模块方法替代二分查找
from bisect import bisect
class solution:
"""
@param A: an integer array
@param target: An integer
@param k: An integer
@return: an integer array
"""
def kClosestNumbers(self, A, target, k):
# write your code here
if not A or not k:
return []
# 查找目标在数组中应该插入的位置
start = bisect(A, target)
lt = rt = start
# 存储最终结果
ans = []
while lt and rt < len(A):
# 由于接近程度相同时，小的数需要排在前面
# 因此先对左边的数进行判断
# 注意，由于右边的数字是不小于目标，
# 而左边的数是小于目标的，因此
# 计算差值时是右边的数字减去目标
# 以及目标减去左边的数字
if target - A[lt - 1] <= A[rt] - target:
ans.append(A[lt - 1])
lt -= 1
else:
ans.append(A[rt])
rt += 1
# 每次循环都判断下是否已经取到了k个数
# 若是，则跳出循环，无需再继续处理
if len(ans) == k:
break
# 循环结束后还未取够k个数
if k - len(ans):
# 计算还差多少个数
pad = k - len(ans)
# 若左边还有数可取，则在左边取够k个数为止
if lt:
ans.extend(A[lt - 1:lt - 1 - pad:-1])
# 否则，在右边取够k个数为止
else:
ans.extend(A[rt:rt + pad])
return ans
网友评论