数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律学C++ 中后缀中不同整数的数量查询
在这个问题中，我们给定一个包含 N 个整数的数组。有 Q 个查询，每个查询包含一个整数值 m。我们的任务是创建一个程序来解决 C++ 中后缀中不同整数的数量查询。
问题描述 - 在这里，我们需要找到从索引 (m-1) 到 (N-1) 的子数组中存在的不同整数的总数。其中 m 是每个查询中的值。
让我们举个例子来理解这个问题 -
输入
array = {2, 6, 1, 2, 7, 6}
Q = 2 , queries = {1, 5}输出
4 2
解释
对于 m = 1，我们需要找到从索引 0 到 N 的不同元素的数量，即 4。
对于 m = 5，我们需要找到从索引 4 到 N 的不同元素的数量，即 2。
解决方案方法
这个问题的解决方案很简单，如示例所示。我们需要简单地计算数组中唯一或不同的元素的数量。如果我们将数据结构视为数组，则似乎很困难。但是，如果我们考虑使用其他数据结构，则解决方案将很容易。
因此，为了解决问题，我们将使用 C++ 中的集合，它在 STL 库中可用。因此，对于每个查询，我们将在集合中插入从索引 (m-1) 到 (n-1) 的元素。集合的长度给出查询的不同元素的数量。
程序说明我们的解决方案，
示例
#include <bits/stdc++.h>
using namespace std;
int findDistinctInt(int arr[], int N, int m) {
set<int> distValues;
for (int i = (N-1); i >= (m-1); i--) {
distValues.insert(arr[i]);
}
return distValues.size();
}
int main() {
int arr[] = { 2, 6, 1, 2, 7, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 2;
int query[Q] = { 1, 5 };
for(int i = 0; i < Q; i++)
cout<<"For query "<<(i+1)<<": The number of distinct integer in Suffix is "<<findDistinctInt(arr, N, query[i])<<endl;
return 0;
}输出
For Query 1: The number of distinct integer in Suffix is 4 For Query 2: The number of distinct integer in Suffix is 2
更新于: 2020年9月9日
79 次浏览
广告