题意
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
注意事项
The value k is a non-negative integer and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 10^4
Absolute value of elements in the array and x will not exceed 10^4
样例
如果 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].
思路
这道题的一般解法都很容易想出来，暴力出奇迹嘛，这里我们只说最优解，也就是 O(logn + k) 的时间复杂度 的解法。
这道题的解题关键是数组A是有序的，只要有序就可以考虑用二分。
我们通过对A进行二分，找到最接近target的数，找到之后用双指针的思想，依次从找到的那个数向两边扩散，直到满足k个数为止。
思路较为简单，编码过程注意一些边界条件的判断即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| 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):
if k == 0:
return []
if not A:
return []
lp = None
rp = None
start = 0
end = len(A) - 1
while start + 1 < end:
mid = int(start + (end - start) / 2)
if A[mid] == target:
start = mid
end = mid + 1
break
elif A[mid] < target:
start = mid
else:
end = mid
if abs(A[start] - target) <= abs(A[start] - target):
lp = start
rp = end
else:
lp = end
rp = end + 1
cnt = 0
ans = list()
while cnt < k:
cnt += 1
if lp < 0 and rp >= len(A):
return []
elif lp < 0:
ans.append(A[rp])
rp += 1
elif rp >= len(A):
ans.append(A[lp])
lp -= 1
elif abs(A[lp] - target) <= abs(A[rp] - target):
ans.append(A[lp])
lp -= 1
else:
ans.append(A[rp])
rp += 1
return ans
|