数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 子数组中不同元素个数的查询
在这个问题中，我们给定一个大小为 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
解释
对于查询 1：l = 1 和 r = 4，子数组[1...4] = {6, 1, 6, 5}，不同元素个数 = 3。
对于查询 2：l = 0 和 r = 6，子数组[0...6] = {5, 6, 1, 6, 5, 2, 1}，不同元素个数 = 4。
解决方案
为了解决这个问题，我们将使用集合数据结构，其长度将给出查询中给定范围的数组中不同元素的个数。对于每个查询，我们将把该范围内数组的所有元素插入到集合中。子数组的所有重复元素都将被丢弃，只存储不同的元素，因此集合的大小将给出不同元素的个数。
程序演示了我们解决方案的工作原理：
示例
#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
更新于：2020年9月9日
浏览量 161 次
广告