समस्या विवरण
इस समस्या में, हमें आकार n का एक ऐरे arr[] और Q क्वेरीज दी गई हैं जिनमें प्रत्येक में 2 मान L और R होते हैं। हमारा कार्य L-वें सबसे छोटे नंबर और R-वें सबसे छोटे नंबर के बीच निरपेक्ष अंतर वापस करने के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।
समस्या विवरण - प्रत्येक क्वेरी को हल करने के लिए, हमें Lवें सबसे छोटे और Rवें सबसे छोटे नंबर का इंडेक्स ढूंढना होगा। और इन इंडेक्स के बीच अंतर ढूंढना होगा।
उदाहरण
arr[] = {8, 4, 1, 5, 2}
Q = 2
Queries[][] = {{2, 4}, {1, 5}}
आउटपुट
1 2
व्याख्या
{2, 4} के लिए: 2वां सबसे छोटा तत्व 2 है जिसका इंडेक्स 4 है
4वां सबसे छोटा तत्व 5 है जिसका इंडेक्स 3 है
अंतर = 4 - 3 = 1
{1, 5} के लिए: सबसे छोटा तत्व 1 है जिसका इंडेक्स 2 है
5वां सबसे छोटा तत्व 8 है जिसका इंडेक्स 0 है
अंतर = 2 - 0 = 2
हल करने का दृष्टिकोण
समस्या को हल करने के लिए, हम एक पेयर बनाएंगे जो ऐरे तत्वों के इंडेक्स और मान को संग्रहीत करेगा। और प्रत्येक क्वेरी के L और R मानों के लिए i-वां सबसे छोटा तत्व ढूंढेंगे। फिर उनके इंडेक्स के निरपेक्ष अंतर को प्रिंट करेंगे।
उदाहरण 1: पेयर डेटा स्ट्रक्चर का उपयोग करके
#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
उदाहरण 2: पेयर के बिना दृष्टिकोण
#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