इस समस्या में, हमें n पूर्णांक मानों का एक सरणी arr[] दिया जाता है। और क्यू प्रश्न करता है कि प्रत्येक में एक पूर्णांक 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
स्पष्टीकरण
For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4. For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3
समाधान दृष्टिकोण
सूचकांक k से n तक शुरू करके प्रत्येक क्वेरी को हल करने के लिए समस्या का एक सरल समाधान। और सरणी के सभी अद्वितीय तत्वों को गिनें और प्रत्येक क्वेरी की गिनती लौटाएं।
प्रभावी समाधान
समस्या का एक प्रभावी समाधान एक पूर्व-गणना डेटा संरचना का उपयोग कर रहा है जो सूचकांक के लिए अद्वितीय गणना को (एन -1) से 0 तक संग्रहीत करता है। यह डुप्लिकेट तत्वों के अतिरिक्त को समाप्त करने के लिए एक अनियंत्रित सेट का उपयोग करके किया जाता है। हम घटना की गिनती के लिए एक सहायक सरणी का भी उपयोग कर सकते हैं।
हम अंतिम से kth तत्व तक अपनी डेटा संरचना में सरणी के तत्वों को जोड़ेंगे और फिर डेटा संरचना में तत्वों की संख्या का पता लगाएंगे (kth अनुक्रमणिका में सरणी मान के मामले में)।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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