資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢兩個陣列的重疊和
在這個問題中，我們得到了兩個包含唯一值的陣列 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(N2)。
解決這個問題的另一種方法是使用雜湊表。我們將建立一個雜湊表，並將兩個陣列的值儲存在表中，並保留元素頻率的計數。然後，將出現頻率為 2 的值新增到總和中。返回總和值的 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
更新於: 2022-02-11
208 次瀏覽
廣告