### 题目

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=3
Output: [1,2,3,4]


Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [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 104
• Absolute value of elements in the array and x will not exceed 104

### 正常人的思路

x = 0
小于等于 大于
<-----|  |----->
... -5, -4, -4, -3, -1, 0, 0, 0, 1, 5, 5, 8 ...


#### 代码

class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int firstGreater = firstGreater(arr, x);
int left = firstGreater - 1, right = firstGreater;
int leftDiff = (left >= 0)? x - arr[left] : 20001;
int rightDiff = (right < arr.length)? arr[right] - x : 20001;
while (k > 0) {
if (leftDiff <= rightDiff) {
leftDiff = (left >= 0)? x - arr[left] : 20001;
} else {
rightDiff = (right < arr.length)? arr[right] - x : 20001;
}
k--;
}
return res;
}

/** find the position of first element greater than given x */
private int firstGreater(int[] arr, int x) {
int size = arr.length;
int lo = 0, hi = size - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] <= x) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return lo;
}
}


### 神仙解法

StefanPochmann提出了一个概念，还是刚才的例子，目标数是x = 0，要取的数字个数是k = 7，结果如下，

x = 0
k = 7

target
|
range     |
|----------------+--|
... -5, -4, -4, -3, -1, 0, 0, 0, 1, 5, 5, 8 ...
|                      |
start                 start + k


x - arr[start] <= arr[start + k] - x

                            target
|
... -5, -4, -4, -3, -1, 0, 0, 0, 1, 5, 5, 8 ...
|                       |
start                 start + k

0 - (-4) > 1 - 0


#### 代码

class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int size = arr.length;
int lo = 0, hi = size - 1 - k;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (x - arr[mid] <= arr[mid + k] - x) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
List<Integer> res = new ArrayList<>();
for (int i = lo; i < lo + k; i++) res.add(arr[i]);
return res;
}
}