समस्या विवरण
इस समस्या में, हमें आकार n का एक सरणी arr[] दिया गया है। और Q क्वेरीज़, जिनमें से प्रत्येक में दो तत्व l और r होते हैं। हमारा कार्य C++ में उपसरणी में विशिष्ट तत्वों की संख्या के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।
यहां प्रत्येक क्वेरी के लिए, हमें arr[l] से arr[r] से शुरू होने वाली उपसरणी में विशिष्ट पूर्णांकों की कुल संख्या ढूंढनी होगी।
उदाहरण
इनपुट
arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}
आउटपुट
3 4
व्याख्या
क्वेरी 1 के लिए: l = 1 और r = 4, उपसरणी[1...4] = {6, 1, 6, 5}, विशिष्ट तत्व = 3।
क्वेरी 2 के लिए: l = 0 और r = 6, उपसरणी[0...6] = {5, 6, 1, 6, 5, 2, 1}, विशिष्ट तत्व = 4।
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हम सेट डेटा संरचना का उपयोग करेंगे, जिसकी लंबाई क्वेरी में दी गई रेंज के लिए सरणी के विशिष्ट तत्वों की संख्या देगी। प्रत्येक क्वेरी के लिए, हम रेंज में सरणी के सभी तत्वों को सेट में सम्मिलित करेंगे। उपसरणी के सभी डुप्लिकेट तत्व हटा दिए जाएंगे और केवल विशिष्ट तत्व संग्रहीत होंगे, इसलिए सेट का आकार विशिष्ट तत्वों की संख्या देगा।
कार्यक्रम उदाहरण
#include<bits/stdc++.h>
using namespace std;
int solveQuery(int arr[], int l, int r) {
set<int> distElements;
for (int i = (r); i >= (l); i--)
distElements.insert(arr[i]);
return distElements.size();
}
int main() {
int arr[] = {5, 6, 1, 6, 5, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int Q = 2;
int query[Q][2] = {{1, 4}, {0,6}};
for(int i = 0; i < Q; i++)
cout << "क्वेरी " << (i+1) << ": उपसरणी में विशिष्ट तत्वों की संख्या " << solveQuery(arr, query[i][0], query[i][1]) << "\n";
return 0;
}
आउटपुट
क्वेरी 1: उपसरणी में विशिष्ट तत्वों की संख्या 3 क्वेरी 2: उपसरणी में विशिष्ट तत्वों की संख्या 4