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 : $$O(n\log n)$$ . Collections.sort() uses binary sort so it has a $$O(n\log n)$$ complexity.

• Space complexity : $$O(k)$$ . 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 : $$O(\log n +k)$$ . $$O(\log n)$$ is for the time of binary search, while $$O(k)$$ is for shrinking the index range to k elements.

• Space complexity : $$O(k)$$ . It is to generate the required sublist.

Analysis written by: @Mr.Bin