資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
