मान लीजिए हमारे पास एक क्रमबद्ध सरणी है, दो पूर्णांक k और x भी दिए गए हैं, हमें उस सरणी में x के k निकटतम तत्व ढूंढने हैं। परिणाम को बढ़ते क्रम में क्रमबद्ध किया जाना चाहिए। यदि टाई है, तो छोटे तत्वों को हमेशा प्राथमिकता दी जाती है। इसलिए यदि इनपुट [1,2,3,4,5] जैसा है और k = 4, x = 3, तो आउटपुट [1,2,3,4] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ans नामक एक सरणी बनाएं
- low := 0 सेट करें, high := सरणी का आकार - k
- जब तक low < high
- mid := low + (high - low) /2
- यदि x - arr[mid] > arr[mid + k] - x, तो low := mid + 1, अन्यथा high := mid
- i को low से low + 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]
