Solution
Approach 1: Using Collection.sort()
Algorithm
Intuitively, we can sort the elements in list arr
by their absolute difference values to the target x
. Then the sublist of the first k elements is the result after sorting the elements by the natural order.
Note: This solution is inspired by @compton_scatter.
Complexity Analysis
-
Time complexity : . Collections.sort() uses binary sort so it has a complexity.
-
Space complexity : . The in-place sorting does not consume any extra space. However, generating a k length sublist will take some space.
Approach 2: Binary Search and Two Pointers
Algorithm
The original array has been sorted so we can take this advantage by the following steps.
1. If the target x
is less or equal than the first element in the sorted array, the first k
elements are the result.
2. Similarly, if the target x
is more or equal than the last element in the sorted array, the last k
elements are the result.
3. Otherwise, we can use binary search to find the index
of the element, which is equal (when this list has x
) or a little bit larger than x
(when this list does not have it). Then set low
to its left k-1
position, and high
to the right k-1
position of this index
as a start. The desired k numbers must in this rang [index-k-1, index+k-1]. So we can shrink this range to get the result using the following rules.
* If low
reaches the lowest index 0
or the low
element is closer to x
than the high
element, decrease the high
index.
* If high
reaches to the highest index arr.size()-1
or it is nearer to x
than the low
element, increase the low
index.
* The looping ends when there are exactly k elements in [low, high], the subList of which is the result.
Complexity Analysis
-
Time complexity : . is for the time of binary search, while is for shrinking the index range to k elements.
-
Space complexity : . It is to generate the required sublist.
Analysis written by: @Mr.Bin