计数对 (p, q) 使得 p 在数组中至少出现 q 次，而 q 在 C++ 中至少出现 p 次

我们得到一个正整数数组。目标是找到 arr[] 元素对的计数，使得对具有元素 ( p, q )，其中 p 在数组中出现至少 q 次，q 在数组中出现至少 p 次。

让我们通过例子来理解。

输入- int arr[] = { 3, 3, 3, 5, 5, 6, 6}

输出- 数组中对的计数，使得一个的频率至少是另一个的值 - 1

说明- 数组中 p 出现 q 次且 q 出现 p 次的有效对是 (3, 3) 因为 3 在数组中出现 3 次。所以只有一对有效，因此计数为 1。

输入- int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6}

输出- 数组中对的计数，使得一个的频率至少是另一个的值 - 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 开始循环 FOR 直到数组的大小

• 在循环内，将 um[arr[i]] 设置为 1 并检查 um 是否为 1，然后将 arr[i] 推入向量中

• 开始另一个循环 FOR 从 0 直到向量的大小并检查 IF um[vec[i] < vec[i] 然后继续，否则如果它们相等则将计数增加 1 ELSE 将计数增加 1。开始另一个循环j FOR 从 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