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