数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中计算数组中满足 LCM(arr[i], arr[j]) > min(arr[i],arr[j]) 的对数
给定一个正整数数组。目标是找到 arr[] 元素对的数量，使得条件 LCM( arr[i], arr[j] ) > min( arr[i], arr[j] ) 成立。也就是说，一对元素的最小公倍数大于两者中的最小值。
注意 - 对 ( arr[i], arr[j] ) 与 ( arr[j],arr[i] ) 相同。不要重复计算。
让我们通过例子来理解。
输入 - arr[] = [ 1,5,4,2 ]
输出 - 满足 LCM(arr[i], arr[j]) > min(arr[i],arr[j]) 的数组中对数为 - 6
解释 - 共有 6 对 -
Pair 1 (1,5) LCM is 5 > 1 Pair 2 (1,4) LCM is 4 > 1 Pair 3 (1,2) LCM is 2 > 1 Pair 4 (5,4) LCM is 20 > 4 Pair 5 (5,2) LCM is 10 > 2 Pair 6 (4,2) LCM is 4 > 2
输入 - arr[] = [ 3,3,6 ]
输出 - 满足 LCM(arr[i], arr[j]) > min(arr[i],arr[j]) 的数组中对数为 - 2
解释 - 共有 2 对 -
Pair 1 (3,6) LCM is 6 > 3 Pair 2 (3,6) LCM is 6 > 3
下面程序中使用的方案如下
只有当 arr[i]==arr[j] 时，上述条件才为假。对将在唯一元素之间形成。使用一个无序映射，其中包含数组唯一元素的频率。现在删除所有相似的元素对。为每个频率计算最大对数为 ( freq * (freq-1)/2 )。将所有此类计算添加到计数中。
总数组大小为元素，则最大对数=size(size-1)/2。
结果将为 pairs-count。（所有对 - 具有相同元素的对）。
获取一个整数数组。
获取一个整数数组。
函数 conditional_pair(int arr[], int size) 获取数组及其大小，并返回满足条件的对数。
将初始计数设为 0。
获取 unordered_map<int, int> um 用于 arr[] 的元素及其频率。
使用 for 遍历映射，对于每个频率 temp = it.second;（it=迭代器）将 temp*(temp-1)/2 添加到计数中。temp 个元素的所有可能对。
现在 count 包含所有相同元素的对，在我们的案例中将不考虑这些对。
计算数组元素的总可能对数为 temp=size*(size-1)/2。
将 count 更新为 count - temp。
返回 count 作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int conditional_pair(int arr[], int size){
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i]]++;
}
for (auto it : um){
int temp = it.second;
count = count + temp * (temp - 1) / 2;
}
int temp = (size * (size - 1)) / 2;
count = temp - count;
return count;
}
int main(){
int arr[] = { 4, 1, 7, 3, 2};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are:
"<<conditional_pair(arr, size);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出 -
Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10
200 次查看
