查询C ++子数组中不同元素的数量

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们得到了大小为n的数组arr []。和Q查询，每个查询由两个元素l和r组成。我们的任务是创建一个程序来解决C ++子数组中不同元素数量的查询。

问题描述-在这里，对于每个查询，我们需要找到子数组中从arr [l]到arr [r]开始的不同整数的总数。

让我们举个例子来了解这个问题，

输入值

arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}

输出结果

3
4

说明

对于Querry 1：l = 1和r = 4，子数组[1 ... 4] = {6，1，6，5}，不同元素= 3。

对于Querry 2 − l = 0和r = 6，子数组[0 ... 6] = {5，6，1，6，5，2，1}，不同元素= 4。

解决方法

为了解决该问题，我们将使用set数据结构，该结构的长度将给出query中给定范围内数组的不同元素的数量。对于每个查询，我们将数组中范围的所有元素插入到集合中。子数组的所有重复元素将被丢弃，并且仅存储不同的元素，因此集合的大小将给出不同元素的数量。

Progam演示了我们解决方案的工作原理，

示例

#include<bits/stdc++.h>
using namespace std;
int solveQuery(int arr[], int l, int r) {
   set<int> distElements;
   for (int i = (r); i >= (l); i--)
   distElements.insert(arr[i]);
   return distElements.size();
}
int main() {
   int arr[] = {5, 6, 1, 6, 5, 2, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   int Q = 2;
   int query[Q][2] = {{1, 4}, {0,6}};
   for(int i = 0; i < Q; i++)
   cout<<"For Query "<<(i+1)<<": The number of distinct elements in subarray is "<<solveQuery(arr,    query[i][0], query[i][1])<<"\n";
   return 0;
}

输出结果

For Query 1: The number of distinct elements in subarray is 3
For Query 2: The number of distinct elements in subarray is 4

以上是 查询C ++子数组中不同元素的数量 的全部内容， 来源链接： utcz.com/z/317068.html

回到顶部