在 C++ 中统计数组中满足以下条件的配对数量：一个元素的频率至少是另一个元素的值

给定一个正整数数组。目标是找到 arr[] 元素对的数量，这些对的元素 (A, B) 满足 A 的频率是 B 的倍数，B 的频率是 A 的倍数。

让我们通过示例来理解。

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

输出 − 数组中满足一个元素的频率至少是另一个元素的值的配对数量为 1

解释 − 数组中 A 出现 B 次且 B 出现 A 次的有效配对是 (3, 3)，因为 3 在数组中出现了 3 次。因此，只有一个有效配对，所以计数为 1。

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

输出 − 数组中满足一个元素的频率至少是另一个元素的值的配对数量为 1

解释 − 数组中 A 出现 B 次且 B 出现 A 次的有效配对是 (3, 3)、(5, 5) 和 (3, 5)，因为 3 在数组中出现了 5 次，而 5 在数组中出现了 3 次。因此，有三个有效配对，所以计数为 3。

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

在这个方案中，我们首先创建一个无序映射，其中包含数组元素的频率。使用 for 循环遍历无序映射。对于每个元素及其频率，如果发现任何频率更多，则增加配对计数。

• 取一个整数数组 arr[]。

• 函数 frequency_other_value(int arr[], int size) 获取数组及其大小，并返回满足以下条件的配对数量：配对是 (A,B)，其中 A 至少出现 B 次，反之亦然。

• 将初始计数设置为 0。

• 取 unordered_map<int, int> um 用于存储 arr[] 的元素及其频率。

• 使用 for 循环遍历映射，对于每对的第一个值 start=it.second;（it=迭代器），使用 for 循环遍历频率 >= start 的映射。

• 为这些配对增加计数。

• 返回计数作为结果。

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
int frequency_other_value(int arr[], int len){
   int count = 0;
   unordered_map<int, int> um;
   for (int i = 0; i < len; ++i){
      um[arr[i]]++;
   }
   for (auto it : um){
      int start = it.first;
      int end = it.second;
      for (int j = 1; j <= end; j++){
         if (um[j] >= start){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 3, 3, 5, 5, 6, 6};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of pairs in an array such that frequency of one is at least value of other are: "<<frequency_other_value(arr, size);
   return 0;
}

输出

如果我们运行以上代码，它将生成以下输出：

Count of pairs in an array such that frequency of one is at least value of other are: 1

Sunidhi Bansal

更新于： 2020-12-02

251 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始