資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中由不同元素子陣列形成的配對計數
給定一個包含整數元素的陣列arr[]。目標是查詢由arr[]的子陣列元素可以形成的配對數量，條件是每個子陣列都只有不同的元素。如果陣列是[1,2,2,3,3]，則只有不同元素的子陣列將是[1,2]和[2,3]。配對將是(1,2)和(2,3)，因此配對計數為2。
讓我們透過例子來理解
輸入 − arr[] = {1,2,5,3}
輸出 − 由不同元素子陣列形成的配對計數為6
解釋 − 具有不同元素的子陣列是：[1,2,5,3]，可能的配對 (1,2)，(1,3)，(1,5)，(2,5)，(2,3)，(5,3)
總共6對。
輸入 − arr[] = {1,2,1,2,3}
輸出 − 由不同元素子陣列形成的配對計數為5
解釋 − 具有不同元素的子陣列為：
[1,2] - pairs: (1,2) [2,1] - pairs: (2,1) [1,2,3] - pairs : (1,2), (2,3), (1,3) Total pairs : 5
下面程式中使用的方法如下
將整數陣列作為輸入。
函式distinct_pairs(int arr[], int size)獲取陣列並返回由不同元素子陣列形成的配對計數。
將初始計數設為0。取變數start=end=0。
取一個向量check(size, false)來標記視窗中的元素。
啟動迴圈WHILE，直到start小於size。
在迴圈內，啟動另一個迴圈WHILE，直到start小於size並且check[arr[start]] = 0，然後將計數設定為start - end，並將check[arr[start]]設定為true，並將其start加1。
啟動迴圈WHILE，直到end小於start並且start不等於size並且check[arr[start]] = true，然後將check[arr[end]]設定為false，並將end加1。
返回計數
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of pairs formed by distinct element sub-arrays are: 17
更新於：2020年12月3日
瀏覽量 107
廣告