Solution

Approach #1 Using Collection.sort( ) [Accepted]

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

\n
• \n

  Time complexity : $$O(n*log(n))$$ . Collections.sort() uses binary sort so it has a $$O(n*log(n))$$ complexity.

  \n
\n
• \n

  Space complexity : $$O(k)$$ . The in-place sorting does not consume any extra space. However, generating a k length sublist will take some space.

  \n
\n

Approach #2 Using Binary Search and Two Pointers [Accepted]

Algorithm

The original array has been sorted so we can take this advantage by the following steps.\n1. If the target x is less or equal than the first element in the sorted array, the first k elements are the result.\n2. Similarly, if the target x is more or equal than the last element in the sorted array, the last k elements are the result.\n3. 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.\n * If low reaches the lowest index 0 or the low element is closer to x than the high element, decrease the high index.\n * If high reaches to the highest index arr.size()-1 or it is nearer to x than the low element, increase the low index.\n * The looping ends when there are exactly k elements in [low, high], the subList of which is the result.

Complexity Analysis

\n
• \n

  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.

  \n
\n
• \n

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

  \n
\n

Analysis written by: @Mr.Bin