数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++程序中后缀中不同整数个数的查询
在这个问题中，我们给定一个包含 n 个整数值的数组 arr[]。以及 Q 个查询，每个查询包含一个整数 k。我们的任务是创建一个程序来解决后缀中不同整数个数的查询。
问题描述 − 我们需要解决后缀中不同整数的查询。对于每个查询，我们需要找到从 k 到 n 的唯一元素的数量，即计算 arr[k] 到 arr[n] 中唯一元素的数量。
所取数组从 1 开始索引。
让我们举个例子来理解这个问题，
输入
arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4}输出
4 4 3
解释
For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4. For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3
解决方案方法
解决此问题的简单方法是从索引 k 到 n 开始解决每个查询。并计算数组的所有唯一元素，并返回每个查询的计数。
有效解决方案
解决此问题的有效方法是使用预先计算的数据结构，该结构存储从 (n-1) 到 0 的索引的唯一计数。这是通过使用无序集合来消除重复元素的添加来完成的。我们甚至可以使用辅助数组来进行出现次数计数。
我们将从最后到第 k 个元素开始将数组的元素添加到我们的数据结构中，然后查找数据结构中元素的数量（在第 k 个索引处的数组值的情况下）。
程序说明我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": the number of distinct integers in Suffix is "<<distIntCount[queries[i]]<<endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
}输出
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
更新于: 2020-12-22
202 次查看
广告