इस लेख में, हमें एक समस्या दी गई है, हमें एक सरणी दी गई है, और दो प्रकार के प्रश्नों के उत्तर देने की आवश्यकता है।
- 0 टाइप करें - हमें x (दिए गए मान) से या उसके बराबर बड़े तत्वों की संख्या की गणना करनी होगी।
- टाइप 1 - हमें x(दिए गए मान) से सख्ती से बड़े तत्वों की संख्या की गणना करनी होगी।
तो यहाँ एक सरल उदाहरण है -
Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
Query 1: 0 50
Query 2: 1 40
Query 3: 0 30
Output :
0
1
3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30. समाधान खोजने के लिए दृष्टिकोण
समाधान खोजने के लिए हम दो अलग-अलग तरीकों का उपयोग कर सकते हैं। सबसे पहले हम जानवर बल समाधान का उपयोग करेंगे और फिर जांच करेंगे कि यह उच्च बाधाओं के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम अपने समाधान को अनुकूलित करने के लिए आगे बढ़ते हैं।
क्रूर फ़ोर्स अप्रोच
इस दृष्टिकोण में, हम सभी q प्रश्नों के लिए सरणी के माध्यम से आगे बढ़ेंगे और दी गई शर्तों को पूरा करने वाली संख्याएं ढूंढेंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // answer
if(!type) { // when type 0 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // when type 1 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] > val)
count++;
}
}
cout << count << "\n";
}
int main() {
int ARR[] = { 10, 15, 30, 40, 45 };
int n = sizeof(ARR)/sizeof(ARR[0]); // size of our array
query(ARR, n, 0, 50); // query 1
query(ARR, n, 1, 40); // query 2
query(ARR, n, 0, 30); // query 3
return 0;
} आउटपुट
0 1 3
उपरोक्त दृष्टिकोण में, हम केवल सरणी के माध्यम से जा रहे हैं और प्रश्नों के उत्तर की गणना कर रहे हैं; यह दृष्टिकोण दिए गए उदाहरणों के लिए काम कर रहा है, लेकिन अगर हम उच्च बाधा का सामना करते हैं, तो यह दृष्टिकोण विफल हो जाएगा क्योंकि कार्यक्रम की समग्र समय जटिलता ओ (एन * क्यू) है जहां एन हमारे सरणी का आकार है और क्यू प्रश्नों की संख्या है इसलिए अब हम इस दृष्टिकोण को इस तरह अनुकूलित करेंगे कि यह उच्च बाधाओं के लिए भी काम करे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम दिए गए मान की ऊपरी सीमा और निचली सीमा को खोजने के लिए द्विआधारी खोज का उपयोग करेंगे। हम पहले बाइनरी सर्च का उपयोग करके अपने एरे को सॉर्ट करते हैं और फिर उसके अनुसार अपने लोअर बाउंड और अपर बाउंड फंक्शन को लागू करते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
cout << "0\n";
else
cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
cout << "0\n";
else
cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // if type == 0 we call lower bound function
lowerbound(arr, n, val);
else // if type == 1 we call upperbound function
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // size of our array
sort(arr, arr+n); // sorting the array
query(arr, n, 0, 5); // query 1
query(arr, n, 1, 3); // query 2
query(arr, n, 0, 3); // query 3
return 0;
} आउटपुट
0 1 2
उपरोक्त कोड एक द्विआधारी खोज पर काम करता है जो हमारे समय की जटिलता को काफी हद तक कम कर देता है। इस प्रकार हमारी अंतिम जटिलता O(NlogN) . बन जाती है , जहां N हमारे सरणी का आकार है।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम दिए गए मान की ऊपरी सीमा और निचली सीमा को खोजने के लिए द्विआधारी खोज का उपयोग करेंगे। अब बाइनरी सर्च के लिए, हम पहले अपने एरे को सॉर्ट करते हैं क्योंकि यह केवल सॉर्ट किए गए एरे के साथ काम करता है। हम अपना निचला बाउंड और अपर बाउंड फ़ंक्शन बनाते हैं जो हमें पहली संख्या खोजने में मदद करता है जो क्रमशः टाइप 0, टाइप 1 शर्तों को संतुष्ट करता है, अब जैसा कि हमने सरणी को सॉर्ट किया है। हमें पहली संख्या मिली जो स्थिति में मदद करती है, इसलिए इस तत्व के बाद के तत्व भी शर्त का पालन करते हैं, इसलिए हम इस तत्व के सूचकांक के अंतर को एन (हमारे सरणी का आकार) के साथ प्रिंट करते हैं।
निष्कर्ष
इस लेख में, हम द्विआधारी खोज का उपयोग करने से कम और अधिक के लिए प्रश्नों को हल करने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।