数据结构
网络
关系数据库管理系统(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
广告