Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or|a - x| == |b - x| and a < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Example 2:
Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]
Constraints:
1 <= k <= arr.length1 <= arr.length <= 104arr is sorted in ascending order.-104 <= arr[i], x <= 104
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
|
import bisect
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
i = bisect.bisect_left(arr, x)
l, r = i - 1, i
while r - l <= k:
if l == -1:
r += 1
elif r == len(arr) or abs(arr[l] - x) <= abs(arr[r] - x):
l -= 1
else:
r += 1
return arr[l+1:r]
'''
Binary search for the left boundary
'''
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
'''
If the element at arr[mid] is closer to x than arr[mid + k],
then that means arr[mid + k], as well as every element to
the right of it can never be in the answer. This means we
should move our right pointer to avoid considering them.
The logic is the same vice-versa - if arr[mid + k] is
closer to x, then move the left pointer.
'''
# Initialize binary search bounds
left = 0
right = len(arr) - k
# Binary search against the criteria described
while left < right:
mid = (left + right) // 2
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
return arr[left:left + k]
|