This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a sorted array, two integers `k`

and `x`

, find the `k`

closest elements to `x`

in the array. The result should also be sorted in ascending order.
If there is a tie, the smaller elements are always preferred.

**Example 1:**

Input:[1,2,3,4,5], k=4, x=3Output:[1,2,3,4]

**Example 2:**

Input:[1,2,3,4,5], k=4, x=-1Output:[1,2,3,4]

**Note:**

- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 10
^{4} - Absolute value of elements in the array and x will not exceed 10
^{4}

**UPDATE (2017/9/19):**

The *arr* parameter had been changed to an **array of integers** (instead of a list of integers). ** Please reload the code definition to get the latest changes**.

b'

\n## Solution

\n

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

\n

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

\n

'
\n\n

\n\n

**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.

\n**Complexity Analysis**

- \n
- \n
Time complexity : . Collections.sort() uses binary sort so it has a complexity.

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

\n \n

\n

**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 : . is for the time of binary search, while is for shrinking the index range to k elements.

\n \n - \n
Space complexity : . It is to generate the required sublist.

\n \n

Analysis written by: @Mr.Bin

\n