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

题意

给一个目标数 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
请博主喝杯咖啡~
0%