Trong bài toán này, chúng ta được cung cấp hai mảng arr1 [] và arr2 [] bao gồm các giá trị duy nhất. Nhiệm vụ của chúng tôi là tìm tổng chồng chéo của hai mảng.
Tất cả các phần tử của mảng là khác biệt. Và chúng ta cần trả về tổng các phần tử chung cho cả hai mảng
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4} Đầu ra
2
Giải thích
The elements that are present in both arrays are 9 and 4. The sum is 9 + 9 + 4 + 4 = 26
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là duyệt qua một mảng, ví dụ arr1 [] và đối với mỗi phần tử, hãy kiểm tra xem có giá trị khớp trong một mảng khác hay không. Nếu tìm thấy bất kỳ phần tử nào khớp với giá trị hiện tại, thì hãy thêm cả hai vào giá trị tổng.
Cách tiếp cận này yêu cầu lồng các vòng lặp dẫn đến độ phức tạp về thời gian của thứ tự O (N 2 ).
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng băm. Chúng tôi sẽ tạo một bảng băm và lưu trữ các giá trị của cả hai mảng trong bảng và giữ nguyên tần suất đếm của các phần tử. Sau đó, thêm giá trị với tần suất xuất hiện hai. Trả lại gấp đôi giá trị tổng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
int findCommonValSum(int A[], int B[], int n){
unordered_map<int,int> hashTable;
for(int i=0;i<n;i++){
if(hashTable.find(A[i])==hashTable.end())
hashTable.insert(make_pair(A[i],1));
else
hashTable[A[i]]++;
if(hashTable.find(B[i])==hashTable.end())
hashTable.insert(make_pair(B[i],1));
else
hashTable[B[i]]++;
}
int commSum = 0;
for(auto itr = hashTable.begin(); itr!=hashTable.end(); itr++){
if((itr->second)==2){
commSum += (itr->first);
}
}
return (commSum*2);
}
int main(){
int A[] = { 5, 4, 9, 2 };
int B[] = { 6, 3, 9, 4 };
int n = sizeof(A) / sizeof(A[0]);
cout<<"The sum of common values in the array are "<<findCommonValSum(A, B, n);
return 0;
} Đầu ra
The sum of common values in the array are 26