समस्या विवरण
इस समस्या में, हमें n पूर्णांक मानों का एक ऐरे arr[] दिया गया है। और Q क्वेरीज जिनमें प्रत्येक में एक पूर्णांक k होता है। हमारा कार्य सफिक्स में विशिष्ट पूर्णांकों की संख्या के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।
समस्या विवरण - हमें सफिक्स में विशिष्ट पूर्णांकों के लिए क्वेरीज को हल करना होगा। प्रत्येक क्वेरी के लिए हमें k से n तक यानी arr[k] से arr[n] तक अद्वितीय तत्वों की संख्या ढूंढनी होगी।
ऐरे 1-इंडेक्स्ड लिया गया है।
उदाहरण
arr[] = {5, 1, 2, 1, 6, 5}, n = 6, Q = 3, query = {1, 3, 4}
आउटपुट
4 4 3
व्याख्या
क्वेरी 1 के लिए: k = 1, N = 6, arr[1] से arr[6] तक तत्वों की गिनती। गिनती = 4। क्वेरी 2 के लिए: k = 3, N = 6, arr[3] से arr[6] तक तत्वों की गिनती। गिनती = 4 क्वेरी 3 के लिए: k = 4, N = 6, arr[4] से arr[6] तक तत्वों की गिनती। गिनती = 3
हल करने का दृष्टिकोण
समस्या का एक सरल हल इंडेक्स k से n से शुरू करके प्रत्येक क्वेरी को हल करना है। और ऐरे के सभी अद्वितीय तत्वों को गिनना और प्रत्येक क्वेरी की गिनती वापस करना।
प्रभावी हल
समस्या का एक प्रभावी हल एक प्रीकंप्यूटेड डेटा स्ट्रक्चर का उपयोग करना है जो (n-1) से 0 तक इंडेक्स के लिए अद्वितीय गिनती संग्रहीत करता है। यह एक अनऑर्डर्ड सेट का उपयोग करके डुप्लिकेट तत्वों के जोड़ को खत्म करके किया जाता है। हम एक सहायक ऐरे का भी उपयोग कर सकते हैं, घटना गिनती के लिए।
हम ऐरे के तत्वों को अपने डेटा स्ट्रक्चर में अंतिम से kवें तत्व तक जोड़ेंगे और फिर डेटा स्ट्रक्चर में तत्वों की गिनती ढूंढेंगे (ऐरे के मामले में kवें इंडेक्स पर मान)।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout << "For Query " << (i+1) << ": the number of distinct integers in Suffix is " << distIntCount[queries[i]] << endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
}
आउटपुट
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
