计算来自两个排序数组的对,这些数组的总和等于C ++中的给定值x

我们给了两个包含正数和值x的数组。目的是找到数组的元素对,以使类型(A,B)的对具有A + B = x且A属于第一个数组,B属于第二个数组。

让我们用例子来理解

输入− arr_1 [] = {1,2,5,3,4}; arr_2 [] = {7,0,1,3}; x = 6

输出-来自两个已排序数组的对数,其总和等于给定值x为-2

解释-对是(5,1)-(arr_1 [2],arr_2 [2])和(3,3)-(arr_1 [3],arr_2 [3])

输入− arr_1 [] = {1,1,1}; arr_2 [] = {2,2}; x = 6

输出-两个总和等于给定值x的排序数组的对数为-2

说明-这些对是(1,2)-(arr_1 [0],arr_2 [0])和(1,2)-(arr_1 [1],arr_2 [1])

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

我们将使用两种方法。第一种使用for循环的幼稚方法。开始使用for循环遍历,这样索引i代表arr_1 [],索引j代表arr_2 []。对于对(arr_1 [i] + arr_2 [j] == x),增加计数。返回计数作为结果。

  • 取整数数组arr_1 []和arr_2 [],其正数元素和长度分别为size_arr_1和size_arr_2。

  • 函数Pair_value_x(int arr_1 [],int arr_2 [],int size_arr_1,int size_arr_2,int x)接受两个数组及其长度,并返回对,以使元素之和为x。

  • 将count的初始值设为0。

  • 开始从i = 0到i <size_arr_1遍历arr_1 []和从j = 0到j遍历arr_2 []

  • 对于每对arr_1 [i],arr_2 [j],检查sum是否为x。如果为true,则增加计数。

  • 返回计数作为结果。

高效方法

在这种方法中,我们将创建arr_1元素的unordered_set。现在,使用for循环遍历arr_2并为每个值arr_2 [i]遍历,如果在集合中找到x-arr_2 [i],则增加计数。最后返回计数。

  • 取相同的数组及其大小。

  • 函数Pair_value_x(int arr_1 [],int arr_2 [],int size_arr_1,int size_arr_2,int x)接受两个数组及其长度,并返回对,以使元素之和为x。

  • 将初始计数设为0。

  • 创建unordered_set <int> hash_map来存储arr_1的唯一元素。

  • 使用for循环使用arr_1的元素填充hash_map。

  • 现在使用for循环遍历arr_2 []。

  • 对于每个arr-2 [j],如果使用(hash_map.find(x-arr_2 [j])!= hash_map.end())在hash_map中找到x-arr_2 [j],则增加计数。

  • 最后,成对计算总和等于x。

  • 返回计数作为结果。

示例(幼稚的方法)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   for (int i = 0; i < size_arr_1; i++){
      for (int j = 0; j < size_arr_2; j++){
         if ((arr_1[i] + arr_2[j]) == x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<<
Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

输出结果

如果我们运行上面的代码,它将生成以下输出-

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4

示例(有效方法)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   unordered_set<int> hash_map;
   for (int i = 0; i < size_arr_1; i++){
      hash_map.insert(arr_1[i]);
   }
   for (int j = 0; j < size_arr_2; j++){
      if (hash_map.find(x - arr_2[j]) != hash_map.end()){
         count++;
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

输出结果

如果我们运行上面的代码,它将生成以下输出-

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4
猜你喜欢