数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究子数组中不同元素的数量查询 | C++ 中的集合 2
在这个问题中，我们得到一个大小为 n 的数组 arr[] 和一个查询。每个查询包含两个值 (L, R)。我们的任务是创建一个程序来解决子数组中不同元素数量的查询。
问题描述 - 在这里，我们需要找到从索引 (L-1) 到 (R-1) 的子数组中存在的不同整数的总数。
让我们举个例子来理解这个问题，
输入
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]输出
4
解释
对于查询 1：L = 1 & R = 4，我们需要找到从索引 0 到 3 的不同元素的数量，即 4。
对于查询 2：L = 2 & R = 6，我们需要找到从索引 1 到 5 的不同元素的数量，即 3。
解决方案方法
解决每个查询的一个简单方法是从 L 到 R 遍历数组并将元素存储到集合中，其大小将给出查询的结果。我们在上一组中讨论过相同的内容。
解决问题的更有效方法是使用线段树数据结构。它将存储给定范围内的不同元素计数。
线段树是一种特殊的树，它以段的形式存储信息。
线段树的叶子节点表示数组的元素。非叶子节点表示具有所需值的段。在这里，它将存储不同的元素。对于这种数据结构的实现，我们将使用 Set。
实现上述解决方案的程序 -
示例
#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;
void CreateSegmentTree(int i, int s, int e, int arr[]) {
if (s == e) {
segmentTree[i].insert(arr[s]);
return;
}
CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
segmentTree[i].insert( segmentTree[2 * i].begin(), segmentTree[2 * i].end());
segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}
set<int> findDistSubarray(int node, int l, int r, int a, int b) {
set<int> left, right, distinctSubarray;
if (b < l || a > r)
return distinctSubarray;
if (a <= l && r <= b)
return segmentTree[node];
left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
distinctSubarray.insert(left.begin(), left.end());
right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
return distinctSubarray;
}
int main() {
int arr[] = {4, 6, 1, 3, 1, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int query[] = {1, 4};
int i = (int)ceil(log2(n));
i = (2 * (pow(2, i))) - 1;
segmentTree = new set<int>[i];
CreateSegmentTree(1, 0, n - 1, arr);
set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
cout<<"The number of distinct elements in the subarray is "<<distCount.size();
return 0;
}输出
The number of distinct elements in the subarray is 4
更新于: 2020年9月9日
359 次浏览
广告