K Closest Elements
MediumBinary Search · Atlassian
You are given an integer array arr sorted in non-decreasing order, and two integers k and x. Return the k elements of arr that are closest to x, sorted in ascending order.
Element a is closer to x than element b if:
|a - x| < |b - x|, or|a - x| == |b - x|anda < b(on a tie, the smaller value wins).
x does not have to appear in arr. If arr contains duplicates, each copy counts as a separate element.
Example 1
- Input:
- arr = [1,3,7,8,12], k = 3, x = 6
- Output:
- [3,7,8]
- Explanation
- Distances from 6 are 5, 3, 1, 2, 6. The three smallest belong to 7, 8 and 3, so the answer, in ascending order, is
[3,7,8].
Example 2
- Input:
- arr = [2,4,6,8], k = 3, x = 5
- Output:
- [2,4,6]
- Explanation
- 4 and 6 are each 1 away and are taken first. For the last slot, 2 and 8 are both 3 away, and the tie goes to the smaller value, 2.
Example 3
- Input:
- arr = [-4,-1,0,5], k = 2, x = 20
- Output:
- [0,5]
- Explanation
xis larger than every element, so the closest values are simply the two largest: 0 and 5.
Constraints
1 <= k <= arr.length <= 10^4arris sorted in non-decreasing order-10^4 <= arr[i], x <= 10^4