資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中統計具有與原始陣列相同總不同元素個數的子陣列
給定一個包含整數的陣列arr[]。目標是統計arr[]的所有子陣列，使得每個子陣列中不同元素的個數與原始陣列中不同元素的個數相同。如果原始陣列是[1,1,2,3]，則子陣列將是[1,2,3]和[1,1,2,3]。
原始陣列中不同的元素總數為3。兩個子陣列中不同的元素總數也為3。
讓我們透過例子來理解。
輸入 − arr[] = {1,2,1,2,3,4,2 };
輸出 − 具有與原始陣列相同總不同元素個數的子陣列數量為 − 6
解釋 − arr[] 中不同的元素有 4 個 (1,2,3,4)。具有相同不同元素個數的子陣列為：（從左到右計數不同元素）
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2 ]
輸入 − arr[] = {8,7,5,6,10 };
輸出 − 具有與原始陣列相同總不同元素個數的子陣列數量為 − 1
解釋 − arr[] 中不同的元素有 5 個 (5,6,7,8,10)。具有相同不同元素個數的子陣列為：（從左到右計數不同元素）[8,7,6,5,10]。只有1個。
下面程式中使用的方法如下
取一個整數陣列arr[]並計算陣列的大小。
函式sub_ele_diff_one(int arr[], int size)接受陣列並返回具有差值為1的連續元素的子陣列計數。
取一個臨時變數count和變數right和left。
取一個無序對映型別變數來建立隨機對。
從0到陣列大小開始FOR迴圈，並在其中設定無序對映中的arr[i]值。
現在，計算無序對映的大小並清除無序對映。
從0到陣列大小開始FOR迴圈。
在迴圈內，直到right < size 和 left < 無序對映大小開始WHILE迴圈
遞增um[arr[right]]的值
現在，檢查如果um[arr[right]] = 1，則將left的值遞增1。
在WHILE迴圈外，將right的值遞增1。
檢查IF left = 無序對映的大小，則將count設定為count + size - right + 1
將um[arr[i]]遞減1
檢查IF um[arr[i]] = 0，則將left遞減1
返回count
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i){
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for(int i = 0; i < size; ++i){
while (right < size && left < um_size){
++um[arr[right]];
if (um[arr[right]] == 1){
++left;
}
++right;
}
if (left == um_size){
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0){
--left;
}
}
return count;
}
int main(){
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of subarrays having total distinct elements same as original array are: 1
182 次瀏覽
