C++中统计数组中存在乘积的数对
给定一个整数型元素数组,任务是从给定数组中形成数对,计算数对中元素的乘积,并检查给定的乘积是否存在于给定数组中。
输入 − int arr[] = {6, 2, 3, 1, 5, 10}
输出 − 乘积存在于同一数组中的数对个数为 − 7
解释 − 从给定数组中可以形成的数对有:(6, 2), (6, 3), (6, 1), (6, 5), (6, 10), (2, 3), (2, 1), (2, 5), (2, 10), (3, 1), (3, 5), (3, 10), (1, 5), (1, 10), (5, 10)。因此,乘积在同一数组中存在的数对为 (2, 3) (乘积为6), (6, 1) (乘积为6), (3, 1) (乘积为3), (2, 5) (乘积为10), (1, 5) (乘积为5), (2, 1) (乘积为2), (1, 10) (乘积为10).
输入 − int arr[] = {2, 4, 8, 5, 10}
输出 − 乘积存在于同一数组中的数对个数为 − 2
解释 − 从给定数组中可以形成的数对有:(2, 4), (2, 8), (2, 5), (2, 10), (4, 8), (4, 5), (4, 10), (8, 5), (8, 10), (5, 10)。因此,乘积在同一数组中存在的数对为 (2, 4) (乘积为8), (2,5) (乘积为10).
下面程序中使用的方法如下
解决给定问题有多种方法,即朴素方法和高效方法。让我们首先看看朴素方法。
输入一个整数元素数组,计算数组的大小并将数据传递给函数。
声明一个名为count的临时变量来存储具有在给定数组中存在的乘积值的数对的数量。
从i=0开始循环到数组大小
在循环内,从j=i+1开始另一个循环到数组大小
在循环内计算乘积为 arr[i] * arr[j]
从k=0开始另一个循环到数组大小
在K循环内,如果乘积 = arr[k],则将计数加1
返回计数
打印结果。
高效方法
输入一个整数元素数组,计算数组的大小并将数据传递给函数。
声明一个名为count的临时变量来存储具有在给定数组中存在的乘积值的数对的数量。
创建一个STL集合类型的变量 pro
从i=0开始循环到数组大小
在循环内,将arr[i]插入到集合变量 pro 中
从i=0开始另一个循环到数组大小
在循环内,从j=i+1开始另一个循环到数组大小
将乘积设置为 arr[i] * arr[j]
如果 pro.find(product) != pro.end(),则将计数加1
返回计数
打印结果。
示例(朴素方法)
#include <bits/stdc++.h> using namespace std; int product_pair(int arr[], int size){ int product = 1; int count = 0; for(int i = 0 ; i<size ; i++){ for(int j = i+1;j<size;j++){ product = arr[i] * arr[j]; for(int pro = 0 ; pro < size; pro++){ if(product == arr[pro]){ count++; } } } } return count; } int main(){ int arr[] = {6, 2, 3, 1, 5, 10}; int size = sizeof(arr)/sizeof(arr[0]); cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size); return 0; }
输出
如果我们运行上面的代码,它将生成以下输出:
Count of pairs whose products exist in same array are: 7
示例(高效方法)
#include<bits/stdc++.h> using namespace std; int product_pair(int arr[], int size){ set< int > pro; int count = 0; int product = 1; for (int i = 0 ; i < size; i++){ pro.insert(arr[i]); } for (int i = 0 ; i < size; i++){ for (int j = i + 1; j < size ; j++){ product = arr[i] * arr[j]; if(pro.find(product) != pro.end()){ count++; } } } return count; } int main(){ int arr[] = {6, 2, 3, 1, 5, 10}; int size = sizeof(arr)/sizeof(arr[0]); cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size); return 0; }
输出
如果我们运行上面的代码,它将生成以下输出:
Count of pairs whose products exist in same array are: 7