在 C++ 中查找 K 个最接近的元素
c++server side programmingprogramming更新于 2025/3/8 21:37:17
假设我们有一个排序数组，还给出了两个整数 k 和 x，我们必须在该数组中找到与 x 最接近的 k 个元素。结果应按升序排序。如果存在平局，则始终优先选择较小的元素。因此，如果输入为 [1,2,3,4,5] 且 k = 4、x = 3，则输出将为 [1,2,3,4]
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个名为 ans 的数组
- 设置 low := 0，high := 数组的大小 – k
- while low < high
- mid := low + (high - low) /2
- if x – arr[mid] > arr[mid + k] – x，则 low := mid + 1，否则 high := mid
- 对于范围 low 到 low + k 内的 i
- 将 arr[i] 插入到 ans 数组中
- return 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]
