मान लीजिए कि हमारे पास एक क्रमबद्ध सरणी है, दो पूर्णांक 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, तो निम्न :=मध्य + 1, अन्यथा उच्च :=मध्य
- i के लिए निम्न से निम्न श्रेणी में + k
- गिरफ्तारी [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]