ในปัญหานี้ เราได้รับอาร์เรย์สองอาร์เรย์ arr1[] และ arr2[] ที่ประกอบด้วยค่าที่ไม่ซ้ำกัน ภารกิจของเราคือ หาผลรวมทับซ้อนของสองอาร์เรย์
องค์ประกอบทั้งหมดของอาร์เรย์ไม่ซ้ำกัน และเราต้องคืนค่าผลรวมขององค์ประกอบที่พบได้ในทั้งสองอาร์เรย์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4}
เอาต์พุต
2
คำอธิบาย
องค์ประกอบที่มีในทั้งสองอาร์เรย์คือ 9 และ 4 ผลรวมคือ 9 + 9 + 4 + 4 = 26
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการเดินทางผ่านอาร์เรย์หนึ่งเช่น arr1[] และสำหรับแต่ละองค์ประกอบตรวจสอบว่ามีค่าที่ตรงกันในอีกอาร์เรย์หนึ่งหรือไม่ หากพบองค์ประกอบใดตรงกับค่าปัจจุบัน ให้เพิ่มทั้งสองเข้าไปในค่าผลรวม
วิธีนี้ต้องการการซ้อนลูปซึ่งทำให้ความซับซ้อนของเวลาเป็น O(N2)
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้แฮชชิง เราจะสร้างตารางแฮชและเก็บค่าของทั้งสองอาร์เรย์ในตารางและเก็บจำนวนความถี่ขององค์ประกอบ จากนั้นบวกค่าที่มีความถี่เกิดขึ้นสองครั้ง คืนค่าสองเท่าของผลรวม
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
