在C ++中查找K个最近的元素
假设我们有一个排序数组，还给出了两个整数k和x，我们必须在该数组中找到k个最接近x的元素。结果应按升序排序。如果有平局，总是首选较小的元素。因此，如果输入像[1,2,3,4,5]并且k=4，x=3，那么输出将是[1,2,3,4]
为了解决这个问题，我们将遵循以下步骤-
创建一个称为ans的数组
设置低：=0，高：=数组大小–k
从低到高
中：=低+（高-低）/2
如果x–arr[mid]>arr[mid+k]–x，则低：=中+1，否则高：=中
对于从低到低+k的范围
将arr[i]插入ans数组
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector <int> ans;
int low = 0;
int high = arr.size() - k;
while(low < high){
int mid = low + (high - low)/2;
if(x - arr[mid] > arr[mid + k] - x){
low = mid + 1;
}
else high = mid;
}
for(int i = low ; i < low + k ; i++)ans.push_back(arr[i]);
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5};
print_vector(ob.findClosestElements(v, 4, 3));
}输入项
[1,2,3,4,5] 4 3
输出结果
[1,2,3,4]