# 658. Find K Closest Elements
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive 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
# Solution
Approach 1: sort array in place by distance to x, then take the first k items. O(NlogN)
time.
Approach 2: binary search for x's insertion point (the index), then use two points to point to both sides of the index. O(logN + k)
time.
# Code (Python)
Approach 2:
import bisect
import collections
class Solution:
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
insert_index = bisect.bisect_left(arr, x)
result = collections.deque()
left, right = insert_index - 1, insert_index
while len(result) < k:
if left < 0:
result.append(arr[right])
right += 1
elif right >= len(arr):
result.appendleft(arr[left])
left -= 1
else:
if x - arr[left] <= arr[right] - x:
result.appendleft(arr[left])
left -= 1
else:
result.append(arr[right])
right += 1
return list(result)
# Code (C++)
Approach 1:
Approach 2: