C++에서 K개의 가장 가까운 요소 찾기

정렬된 배열이 있고 두 개의 정수 k와 x도 주어진다고 가정하면 해당 배열에서 x에 가장 가까운 k 요소를 찾아야 합니다. 결과는 오름차순으로 정렬되어야 합니다. 동점인 경우 항상 더 작은 요소가 선호됩니다. 따라서 입력이 [1,2,3,4,5]이고 k =4, x =3이면 출력은 [1,2,3,4]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• as라는 배열을 만듭니다.
• set low :=0, high :=배열 크기 – k
• 낮은 동안 <높음
  • 중간 :=낮음 + (높음 - 낮음) /2
  • if x – arr[mid]> arr[mid + k] – x이면 low :=mid + 1, 그렇지 않으면 high :=mid
• 낮은 범위에서 i의 경우 + k
  • arr[i]를 as 배열에 삽입
• 반환

예(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]