Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.
Assumptions:
A is not null
K is guranteed to be >= 0 and K is guranteed to be <= A.length
Return:
A size K integer array containing the K closest numbers(not indices) in A, sorted in ascending order by the difference between the number and T.
Examples:
A = {1, 2, 3}, T = 2, K = 3, return {2, 1, 3} or {2, 3, 1}
A = {1, 4, 6, 8}, T = 3, K = 3, return {4, 1, 6}
class Solution(object):
def kClosest(self, array, target, k):
A = array
if not A or k ==0:
return []
res = []
index = self.binarySearch(A,target)
res.append(A[index])
k -= 1
left = index - 1
right = 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):
low = 0
high = len(L) - 1
while low < high - 1:
mid = (low + high)/2
if L[mid] == target:
return mid
elif L[mid] > target:
high = mid
else: low = mid
return low if abs(L[low] - target) <= abs(L[high] - target) else high
