在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]