# [LeetCode] 658. Find K Closest Elements 寻找K个最近元素

2021年09月15日 阅读数：1

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

Example 1:java

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

Example 2:python

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

Note:数组

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 104
3. Absolute value of elements in the array and x will not exceed 104

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

Java:htm

```public List<Integer> findClosestElements(int[] A, int k, int x) {
int left = 0, right = A.length - k;
while (left < right) {
int mid = (left + right) / 2;
if (x - A[mid] > A[mid + k] - x)
left = mid + 1;
else
right = mid;
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < k; i++) res.add(A[left + i]);
return res;
}　　```

Java:blog

```public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int index = Collections.binarySearch(arr, x);
if(index < 0) index = -(index + 1);
int i = index - 1, j = index;
while(k-- > 0){
if(i<0 || (j<arr.size() && Math.abs(arr.get(i) - x) > Math.abs(arr.get(j) - x) ))j++;
else i--;
}
return arr.subList(i+1, j);
}　```

Java:

```public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int lo = 0, hi = arr.size() - k;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x - arr.get(mid) > arr.get(mid+k) - x)
lo = mid + 1;
else
hi = mid;
}
return arr.subList(lo, lo + k);
}
```

Python:

```def findClosestElements(self, A, k, x):
left, right = 0, len(A) - k
while left < right:
mid = (left + right) / 2
if x - A[mid] > A[mid + k] - x:
left = mid + 1
else:
right = mid
return A[left:left + k]　　```

Python:

```import bisect

class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
i = bisect.bisect_left(arr, x)
left, right = i-1, i
while k:
if right >= len(arr) or \
(left >= 0 and abs(arr[left]-x) <= abs(arr[right]-x)):
left -= 1
else:
right += 1
k -= 1
return arr[left+1:right]
```

Python:

```def findClosestElements(self, arr, k, x):
left = right = bisect.bisect_left(arr, x)
while right - left < k:
if left == 0: return arr[:k]
if right == len(arr): return arr[-k:]
if x - arr[left - 1] <= arr[right] - x: left -= 1
else: right += 1
return arr[left:right]　```

C++:

```class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> res = arr;
while (res.size() > k) {
int first  = 0, last = res.size() - 1;
if (x - res.front() <= res.back() - x) {
res.pop_back();
} else {
res.erase(res.begin());
}
}
return res;
}
};
```

C++:

```class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = left + (right - left) / 2;
if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
else right = mid;
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
};
```

C++:

```vector<int> findClosestElements(vector<int>& A, int k, int x) {
int left = 0, right = A.size() - k;
while (left < right) {
int mid = (left + right) / 2;
if (x - A[mid] > A[mid + k] - x)
left = mid + 1;
else
right = mid;
}
return vector<int>(A.begin() + left, A.begin() + left + k);
}
```