数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 统计满足条件的 (p, q) 对数：p 在数组中至少出现 q 次，q 在数组中至少出现 p 次。
给定一个正整数数组。目标是找到数组元素对的数量，这些元素对具有元素 (p, q)，其中 p 在数组中至少出现 q 次，而 q 在数组中至少出现 p 次。
让我们通过例子来理解。
输入 − int arr[] = { 3, 3, 3, 5, 5, 6, 6}
输出 − 数组中满足条件的 (p,q) 对的数量为 1
解释 − 数组中满足 p 至少出现 q 次且 q 至少出现 p 次的有效对是 (3, 3)，因为 3 在数组中出现了 3 次。因此只有一个有效对，计数为 1。
输入 − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6}
输出 − 数组中满足条件的 (p,q) 对的数量为 1
解释 − 数组中满足 p 至少出现 q 次且 q 至少出现 p 次的有效对是 (3, 3), (5, 5) 和 (3, 5)，因为 3 出现了 5 次，而 5 出现了 3 次。因此有三个有效对，计数为 3。
下面程序中使用的方法如下
输入一个整数元素数组，计算数组大小，并将数据传递给函数以进行进一步处理。
声明一个临时变量 count 来存储 p 和 q 的出现次数。
创建一个 vector 类型的变量 vec 和 unordered_map 类型的变量 um。
从 0 开始循环到数组大小。
在循环内，将 um[arr[i]] 设置为 1，并检查 IF um 为 1，则将 arr[i] 推入向量。
从 0 开始另一个循环到向量的长度，并检查 IF um[vec[i] < vec[i] 则继续，ELSE IF 它们相等，则将计数加 1，ELSE 将计数加 1。从 j 开始另一个循环 j 到 vec[i] + 1 直到 um[vec[i]]。
在循环 j 内，检查 IF um[j] >= vec[i]，则将计数加 1。
返回计数。
打印结果。
示例
#include <bits/stdc++.h>
using namespace std;
int pair_count(int arr[], int len){
int count = 0;
vector<int> vec;
unordered_map<int, int> um;
for (int i = 0; i < len; i++){
um[arr[i]]++;
if (um[arr[i]] == 1){
vec.push_back(arr[i]);
}
}
for (int i = 0; i < vec.size(); i++){
if (um[vec[i]] < vec[i]){
continue;
}
else if (um[vec[i]] == vec[i]){
count++;;
}
else{
count++;
for (int j = vec[i] + 1; j <= um[vec[i]]; j++){
if (um[j] >= vec[i]){
count++;
}
}
}
}
return count;
}
int main(){
int arr[] = { 1, 1, 1, 5, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least
p times are: "<<pair_count(arr, size);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1
浏览量 189 次
