在C ++中查找K个最近的元素

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个排序数组，还给出了两个整数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]

以上是 在C ++中查找K个最近的元素 的全部内容， 来源链接： utcz.com/z/326764.html

回到顶部