資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告