C++를 사용하여 두 배열의 겹치는 합 찾기

이 문제에서는 고유한 값으로 구성된 두 개의 배열 rr1[]과 rr2[]가 제공됩니다. 우리의 임무는 두 배열의 겹치는 합을 찾는 것입니다.

배열의 모든 요소는 고유합니다. 그리고 두 배열에 공통인 요소의 합을 반환해야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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