数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告