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

更新于:2020年10月31日

浏览量 124

启动你的职业生涯

完成课程获得认证

开始学习
广告