ধরুন আমাদের একটি সাজানো অ্যারে আছে, দুটি পূর্ণসংখ্যা k এবং xও দেওয়া আছে, আমাদের সেই অ্যারেতে 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, তারপর low :=mid + 1, অন্যথায় high :=mid
- আমি নিম্ন থেকে নিম্ন + k
- পরিসরে
- ans অ্যারেতে arr[i] ঢোকান
- উত্তর ফেরত দিন
উদাহরণ(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]
