Chúng ta được cung cấp hai mảng chứa các số dương và một giá trị x. Mục đích là tìm các cặp phần tử của mảng sao cho các cặp kiểu (A, B) có A + B =x và A thuộc mảng đầu tiên và B thuộc mảng thứ hai.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr_1 [] ={1,2,5,3,4}; arr_2 [] ={7,0,1,3}; x =6
Đầu ra −Tổng số các cặp từ hai mảng đã sắp xếp có tổng bằng một giá trị x cho trước là - 2
Giải thích - Các cặp là (5,1) - (arr_1 [2], arr_2 [2]) và (3,3) - (arr_1 [3], arr_2 [3])
Đầu vào - arr_1 [] ={1,1,1}; arr_2 [] ={2,2}; x =6
Đầu ra - Đếm các cặp từ hai mảng đã sắp xếp có tổng bằng một giá trị x cho trước là - 2
Giải thích - Các cặp là (1,2) - (arr_1 [0], arr_2 [0]) và (1,2) - (arr_1 [1], arr_2 [1])
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ sử dụng hai cách tiếp cận. Cách tiếp cận ngây thơ đầu tiên bằng cách sử dụng vòng lặp for. Bắt đầu duyệt qua cả hai vòng lặp for sao cho chỉ mục i dành cho arr_1 [] và chỉ mục j dành cho arr_2 []. Đối với cặp (arr_1 [i] + arr_2 [j] ==x), số gia tăng. Kết quả là số lượt trả lại.
-
Lấy mảng số nguyên arr_1 [] và arr_2 [] với các phần tử dương và độ dài là size_arr_1 và size_arr_2.
-
Hàm Pair_value_x (int arr_1 [], int arr_2 [], int size_arr_1, int size_arr_2, int x) nhận cả mảng và độ dài của chúng và trả về các cặp sao cho tổng các phần tử là x.
-
Lấy giá trị ban đầu của số đếm là 0.
-
Bắt đầu đi ngang arr_1 [] từ i =0 đến i
-
Đối với mỗi cặp arr_1 [i], arr_2 [j], hãy kiểm tra xem tổng có phải là x hay không. Nếu đúng, hãy đếm gia số.
-
Kết quả là số lượt trả lại.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ tạo một tập hợp không có thứ tự các phần tử của arr_1. Bây giờ duyệt arr_2 bằng vòng lặp for và cho mỗi giá trị arr_2 [i], nếu x-arr_2 [i] được tìm thấy trong tập hợp thì số gia tăng. Số lượt trả lại khi kết thúc.
-
Lấy các mảng giống nhau và kích thước của chúng.
-
Hàm Pair_value_x (int arr_1 [], int arr_2 [], int size_arr_1, int size_arr_2, int x) nhận cả mảng và độ dài của chúng và trả về các cặp sao cho tổng các phần tử là x.
-
Lấy số lượng ban đầu là 0.
-
Tạo unsrdered_set
hash_map để lưu trữ các phần tử duy nhất của arr_1. -
Điền hash_map với các phần tử của arr_1 bằng vòng lặp for.
-
Bây giờ đi ngang qua arr_2 [] bằng vòng lặp for.
-
Đối với mỗi arr-2 [j], nếu x-arr_2 [j] được tìm thấy trong hash_map bằng cách sử dụng (hash_map.find (x - arr_2 [j])! =Hash_map.end ()), thì số gia tăng.
-
Cuối cùng được tính là các cặp có tổng bằng x.
-
Kết quả là số lượt trả lại.
Ví dụ (cách tiếp cận ngây thơ)
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4
Ví dụ (Phương pháp Tiếp cận Hiệu quả)
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4