数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中具有最大不同元素的子序列计数
给定一个仅包含整数的数组 arr[]。目标是找到 arr[] 的子序列的数量，这些子序列具有最大数量的不同元素。如果数组是 [ 4,1,2,3,4 ]，则两个子序列将是 [ 4,1,2,3 ] 和 [ 1,2,3,4 ]。
让我们通过示例来理解
输入 − arr[]= { 1,3,5,4,2,3,1 }
输出 − 具有最大不同元素的子序列的计数为 - 4
解释 − 最大不同的元素是 1、2、3、4 和 5。计数为 5。子序列将为 -
[ 1,3,5,4,2 ], [ 3,5,4,2,1], [ 5,4,2,3,1 ], [ 1,5,4,2,3 ].
输入 − arr[]= { 5,4,2,1,3 }
输出 − 具有最大不同元素的子序列的计数为 - 1
解释 − 所有元素都是不同的。子序列的数量将为 1。
下面程序中使用的方法如下
在这种方法中，我们将基于以下事实找到子序列：如果所有元素都不同，则子序列的数量为 1，即数组本身。如果存在重复元素，则每个重复元素将是新子序列的一部分。因此，我们将创建一个无序映射，用于存储不同元素的频率。然后，对于每个频率，将该频率乘以计数。最后，count 有一个总频率数。
将整数数组 arr[] 作为输入。
函数 Max_distinct_subseq(int arr[], int size) 获取数组及其大小，并返回具有最大不同元素的子序列的计数。
将初始计数设置为 1，因为如果所有元素都不同，则数组本身就是具有最大不同元素的子序列。
创建 unordered_map<int, int> hash; 以存储所有不同元素的频率。
使用 for 循环遍历数组，并使用 hash[arr[i]]]++ 更新每个元素 arr[i] 的频率。
现在使用 for 循环遍历哈希。对于每个频率 it->second(it=迭代器)，将其乘以先前的计数。因为相同时间的 x 个元素将是 x 个不同子序列的一部分。
最后，count 有一个总频率数。
返回 count 作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
int count = 1;
unordered_map<int, int> hash;
for (int i = 0; i < size; i++){
hash[arr[i]]++;
}
for (auto it = hash.begin(); it != hash.end(); it++){
count = count * (it->second);
}
return count;
}
int main(){
int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出 -
Count of subsequences having maximum distinct elements are: 3
252 次浏览
