इस समस्या में, हमें आकार n और Q प्रश्नों की एक सरणी arr[] दी जाती है, जिनमें से प्रत्येक में 2 मान L और R होते हैं। हमारा कार्य प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है जो L-वें सबसे छोटी संख्या और के बीच पूर्ण अंतर को वापस कर सके। आर-वें सबसे छोटी संख्या।
समस्या का विवरण - प्रत्येक प्रश्न को हल करने के लिए, हमें Lth सबसे छोटी और Rth सबसे छोटी संख्या का सूचकांक ज्ञात करना होगा। और इन सूचकांकों में अंतर ज्ञात कीजिए।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}} आउटपुट
1 2
स्पष्टीकरण
For {2, 4}: 2nd smallest element is 2 whose index is 4
4th smallest element is 5 whose index is 3 Difference = 4 - 3 = 1
For {1, 5} Smallest element is 1 whose index is 2
5th smallest element is 8 whose index is 0 Difference = 2 - 0 = 2 समाधान दृष्टिकोण
समस्या को हल करने के लिए, हम एक जोड़ी बनाएंगे जो सरणी तत्वों के सूचकांक और मूल्यों को संग्रहीत करेगा। और प्रत्येक क्वेरी के एल और आर दोनों मानों के लिए i-th सबसे छोटा तत्व खोजें। फिर उनके सूचकांकों का पूर्ण अंतर प्रिंट करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
pair<int, int> arrayIndex[n];
for (int i = 0; i < n; i++) {
arrayIndex[i].first = arr[i];
arrayIndex[i].second = i;
}
sort(arrayIndex, arrayIndex + n);
for (int i = 0; i < Q; i++){
int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries);
return 0;
} आउटपुट
For Query 1: Difference is 1 For Query 2: Difference is 2
यह प्रोग्राम जोड़ी डेटा संरचना का उपयोग करता है लेकिन एक समाधान है जो इसका उपयोग किए बिना अंतर ढूंढ सकता है। इसके लिए, हम एक ऐरे का उपयोग करेंगे जो तत्वों को आरोही क्रम में संग्रहीत करेगा। और फिर प्रत्येक क्वेरी के लिए एल और आर के दोनों मानों के लिए ith सबसे छोटा तत्व खोजना। फिर उनके सूचकांकों का अंतर ज्ञात कीजिए।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
for(int i = 0; i < n; i++)
if(arr[i] == ele)
return i;
return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
int Lele = minArray[L-1];
int Rele = minArray[R-1];
int index1 = searchEle(arr, Lele, n);
int index2 = searchEle(arr, Rele, n);
return abs(index1 - index2);
}
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
int minArray[n];
for (int i = 0; i < n; i++)
minArray[i] = arr[i];
sort(minArray, minArray + n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n, queries[i][0], queries[i][1])<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries); return 0;
} आउटपुट
For Query 1: Difference is 1 For Query 2: Difference is 2