इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है और हमें एक्वेरी दिया जाता है। प्रत्येक क्वेरी में दो मान (L, R) होते हैं। हमारा काम एक सबरे में अलग-अलग तत्वों की संख्या के लिए प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है
समस्या का विवरण - यहां, हमें इंडेक्स (L-1) से (R-1) तक सबएरे में मौजूद अलग-अलग पूर्णांकों की कुल संख्या का पता लगाना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4] आउटपुट
4
स्पष्टीकरण
क्वेरी 1 के लिए:एल =1 और आर =4, हमें इंडेक्स 0 से 3 तक के विशिष्ट तत्वों की संख्या ज्ञात करनी होगी, जो कि 4 है।
क्वेरी 2 के लिए:एल =2 और आर =6, हमें इंडेक्स 1 से 5 तक अलग-अलग तत्वों की संख्या ज्ञात करनी होगी, जो कि 3 है।
समाधान दृष्टिकोण
प्रत्येक क्वेरी को हल करने के लिए एक सरल तरीका यह है कि सरणी को एल से रैंड स्टोर तत्वों तक सेट में पार किया जाए, जिसका आकार क्वेरी का परिणाम देगा। वही हमने पिछले सेट में चर्चा की है।
समस्या को हल करने का एक अधिक प्रभावी तरीका सेगमेंट ट्री डेटास्ट्रक्चर का उपयोग करना है। यह दी गई श्रेणी के लिए विशिष्ट तत्व गणना को संग्रहीत करेगा।
खंड का पेड़ एक विशेष प्रकार का पेड़ है, जो जानकारी को खंडों के रूप में संग्रहीत करता है।
खंड वृक्ष का पत्ता नोड सरणी के तत्वों को दर्शाता है। और गैर-पत्ती नोड्स आवश्यक मान वाले खंडों को दर्शाते हैं। यहां, यह विशिष्ट तत्वों को संग्रहीत करेगा। इस डेटा संरचना के कार्यान्वयन के लिए, हम सेट का उपयोग करेंगे।
उपरोक्त समाधान की कार्यप्रणाली को लागू करने के लिए कार्यक्रम -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;
void CreateSegmentTree(int i, int s, int e, int arr[]) {
if (s == e) {
segmentTree[i].insert(arr[s]);
return;
}
CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
segmentTree[i].insert( segmentTree[2 * i].begin(), segmentTree[2 * i].end());
segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}
set<int> findDistSubarray(int node, int l, int r, int a, int b) {
set<int> left, right, distinctSubarray;
if (b < l || a > r)
return distinctSubarray;
if (a <= l && r <= b)
return segmentTree[node];
left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
distinctSubarray.insert(left.begin(), left.end());
right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
return distinctSubarray;
}
int main() {
int arr[] = {4, 6, 1, 3, 1, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int query[] = {1, 4};
int i = (int)ceil(log2(n));
i = (2 * (pow(2, i))) - 1;
segmentTree = new set<int>[i];
CreateSegmentTree(1, 0, n - 1, arr);
set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
cout<<"The number of distinct elements in the subarray is "<<distCount.size();
return 0;
} आउटपुट
The number of distinct elements in the subarray is 4