在这个问题中,我们得到了大小为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