好资源导航 » 文章资讯 » 计数对 (p, q) 使得 p 在数组中至少出现 q 次，而 q 在 C++ 中至少出现 p 次

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

2023-06-21 14:30:04 68

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

让我们通过例子来理解。

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

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

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

输入-intarr[]={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直到向量的大小并检查IFum[vec[i]

在循环内j检查IFum[j]>=vec[i]然后将计数增加1

返回计数

打印结果。

示例

#include 
using namespace std;
int pair_count(int arr[], int len){
   int count = 0;
   vector vec;
   unordered_map 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: "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1

返回顶部
514930285
czq8825@qq.com

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

下面程序中使用的方法如下

示例

热门推荐

随机推荐