Tìm K phần tử gần nhất trong C ++

Giả sử chúng ta có một mảng đã sắp xếp, hai số nguyên k và x cũng cho trước, chúng ta phải tìm k phần tử gần nhất với x trong mảng đó. Kết quả nên được sắp xếp theo thứ tự tăng dần. Nếu có sự ràng buộc, các yếu tố nhỏ hơn luôn được ưu tiên. Vì vậy, nếu đầu vào là [1,2,3,4,5] và k =4, x =3, thì đầu ra sẽ là [1,2,3,4]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng được gọi là ans
• đặt low:=0, high:=size của mảng - k
• trong khi thấp
• giữa:=low + (cao - thấp) / 2
• if x - arr [mid]> arr [mid + k] - x thì low:=mid + 1, ngược lại high:=mid

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,2,3,4,5]
4
3

Đầu ra

[1,2,3,4]