在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