查询C ++中后缀中不同整数的数量

在这个问题中，我们得到了N个整数的数组。有Q个查询，每个查询包含一个整数值m。我们的任务是创建一个程序来解决C ++中后缀中不同整数的查询。

问题描述-在这里，我们将需要找到从索引(m-1)到(N-1)的子数组中存在的不同整数的总数。其中，m是每个查询中的值。

让我们以一个例子来了解问题-

输入值

array = {2, 6, 1, 2, 7, 6}
Q = 2 , queries = {1, 5}

输出结果

4 2

说明

对于m = 1，我们需要找到从索引0到N的不同元素的数量，即4。

对于m = 5，我们需要找到从索引4到N的不同元素的数量，即2。

解决方法

如示例中所示，此问题的解决方案很简单。我们只需要简单地计算数组中唯一或不同元素的数量即可。如果我们将数据结构考虑为数组，这似乎很困难。但是，如果考虑使用其他数据结构，该解决方案将很容易。

因此，为了解决该问题，我们将使用S ++库中可用的C ++中的集合。因此，对于每个查询，我们都将从索引(m-1)到(n-1)的元素插入集合中。集合的长度给出了查询中不同元素的数量。

程序来说明我们的解决方案，

示例

#include <bits/stdc++.h>
using namespace std;

int findDistinctInt(int arr[], int N, int m) {

   set<int> distValues;
   for (int i = (N-1); i >= (m-1); i--) {
      distValues.insert(arr[i]);
   }
   return distValues.size();
}

int main() {

   int arr[] = { 2, 6, 1, 2, 7, 6 };
   int N = sizeof(arr) / sizeof(arr[0]);
   int Q = 2;
   int query[Q] = { 1, 5 };

   for(int i = 0; i < Q; i++)
   cout<<"For query "<<(i+1)<<": The number of distinct integer in Suffix is "<<findDistinctInt(arr,    N, query[i])<<endl;

   return 0;
}

输出结果

For Query 1: The number of distinct integer in Suffix is 4
For Query 2: The number of distinct integer in Suffix is 2