在C ++程序中查询后缀中不同整数的数量
在这个问题中，我们得到了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, Count of elements from arr[1] to arr[6]. Count = 4. 查询 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 查询 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 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<<"查询 "<<(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;
}输出结果查询 1: the number of distinct integers in Suffix is 4 查询 2: the number of distinct integers in Suffix is 4 查询 3: the number of distinct integers in Suffix is 3