ในปัญหานี้ เราได้รับสองอาร์เรย์ arr1[] และ arr2[] ซึ่งประกอบด้วยค่าที่ไม่ซ้ำกัน งานของเราคือ ค้นหาผลรวมที่ทับซ้อนกันของสองอาร์เรย์
องค์ประกอบทั้งหมดของอาร์เรย์มีความแตกต่างกัน และเราจำเป็นต้องคืนค่าผลรวมขององค์ประกอบที่เหมือนกันสำหรับทั้งสองอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4} ผลผลิต
2
คำอธิบาย
The elements that are present in both arrays are 9 and 4. The sum is 9 + 9 + 4 + 4 = 26
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสำรวจอาร์เรย์หนึ่งอาร์เรย์ว่า arr1[] และสำหรับแต่ละองค์ประกอบให้ตรวจสอบว่ามีค่าที่ตรงกันในอาร์เรย์อื่นหรือไม่ หากพบองค์ประกอบใดๆ ที่ตรงกับค่าปัจจุบัน ให้เพิ่มทั้งคู่ลงในค่าผลรวม
วิธีการนี้ต้องการการซ้อนลูปที่นำไปสู่ความซับซ้อนของเวลาของลำดับ O(N 2 )
แนวทางอื่นในการแก้ปัญหาคือการใช้การแฮช เราจะสร้างตารางแฮชและเก็บค่าของอาร์เรย์ทั้งสองไว้ในตารางและเก็บจำนวนความถี่ขององค์ประกอบไว้ แล้วบวกค่าที่มีความถี่เกิดขึ้นสอง ส่งกลับค่าผลรวมสองเท่า
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The sum of common values in the array are 26
