377. K Nearest Readings
A sensor log stores readings in sorted order. An engineer picks a reference value x and wants the k readings that are closest to it, where closeness is the absolute difference between a reading and x.
Given the sorted array nums, return those k readings in ascending order. When two readings are equally close to x, prefer the smaller reading. The log can hold hundreds of thousands of values, so sorting by distance (O(n log n)) is more than you need: the winners always form one block of neighbouring entries, and you can find where it starts with binary search.
Example 1
- Input:
- nums = [2,5,6,9,14], k = 2, x = 7
- Output:
- [5,6]
- Explanation:
Distances from 7 are: 5 gives 2, 6 gives 1, 9 gives 2. After 6, the readings 5 and 9 tie at distance 2 and the smaller one wins, giving [5, 6].
Example 2
- Input:
- nums = [1,2,3], k = 3, x = 100
- Output:
- [1,2,3]
- Explanation:
All three readings are needed.
Constraints
1 ≤ k ≤ nums.length ≤ 106
-108 ≤ nums[i], x ≤ 108nums is sorted in non-decreasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log(n - k) + k)
- Space
- O(1) extra, plus the output