นับคู่จากสองอาร์เรย์ที่จัดเรียงซึ่งมีผลรวมเท่ากับค่าที่กำหนด x ใน C++

เราได้รับอาร์เรย์สองอาร์เรย์ที่มีจำนวนบวกและค่า 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 loop เริ่มสำรวจทั้งโดยใช้ for loops โดยที่ index i ใช้สำหรับ arr_1[] และ index 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

• ใช้ค่าเริ่มต้นนับเป็น 0

• เริ่มสำรวจ arr_1[] จาก i=0 ถึง i

• สำหรับแต่ละคู่ arr_1[i], arr_2[j] ให้ตรวจสอบว่าผลรวมเป็น x หรือไม่ ถ้าเป็นจริง นับเพิ่ม

• ผลตอบแทนนับเป็นผลลัพธ์

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้ เราจะสร้าง unordered_set ขององค์ประกอบ arr_1 ตอนนี้สำรวจ arr_2 โดยใช้ for loop และสำหรับแต่ละค่า 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 hash_map สำหรับจัดเก็บองค์ประกอบเฉพาะของ arr_1

• เติม hash_map ด้วยองค์ประกอบของ arr_1 โดยใช้ for loop

• ตอนนี้ให้ข้าม arr_2[] โดยใช้ for loop

• สำหรับแต่ละ arr-2[j] หากพบ x-arr_2[j] ใน hash_map โดยใช้ (hash_map.find(x - arr_2[j]) !=hash_map.end()) ให้นับจำนวนที่เพิ่มขึ้น

• ในตอนท้ายนับเป็นคู่ที่มีผลรวมเท่ากับ 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