इस समस्या में, हमें 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 के लिए - एल =0 और आर =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<<"For Query "<<(i+1)<<": The number of distinct elements in subarray is "<<solveQuery(arr, query[i][0], query[i][1])<<"\n";
return 0;
} आउटपुट
For Query 1: The number of distinct elements in subarray is 3 For Query 2: The number of distinct elements in subarray is 4