C ++中具有最大不同元素的子序列数

  • Z时代
  • 2024-01-10
  • 分类：综合

给我们一个仅包含整数的数组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，即数组本身。如果存在重复的元素，则每个重复的元素将成为新子序列的一部分。因此，我们将创建一个不同元素的频率的unordered_map。然后将每个频率乘以该频率进行计数。最后，计数具有频率总数。

  • 以整数数组arr []作为输入。

  • 函数Max_distinct_subseq（int arr []，int size）获取数组及其大小，并返回具有最大不同元素的子序列的计数。

  • 假设所有元素都是唯一的，则将初始计数设为1，则数组本身是具有最大不同元素的子序列。

  • 创建unordered_map <int，int>哈希值；存储所有不同元素的频率。

  • 使用for循环遍历数组，并使用hash [arr [i]]] ++更新每个元素arr [i]的频率。

  • 现在，使用for循环遍历哈希。对于每个频率，它-> second（it = iterator）乘以先前的计数。由于同一时间的x个元素将成为x个不同子序列的一部分。

  • 最后，计数具有频率总数。

  • 返回计数作为结果。

示例

#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

以上是 C ++中具有最大不同元素的子序列数 的全部内容， 来源链接： utcz.com/z/340770.html

回到顶部