C++ 中三个有序数组的交集
c++server side programmingprogramming更新于 2025/6/27 8:52:17
假设有三个整数数组 arr1、arr2 和 arr3，它们按严格升序排序，我们需要返回一个仅包含这三个数组中都出现过的整数的有序数组。因此，如果数组为 [1,2,3,4,5]、[1,2,5,7,9] 和 [1,3,4,5,8]，则输出为 [1,5]
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为 res 的数组
- 创建三个映射 f1、f2 和 f3
- for i，范围从 0 到 arr1 的长度
- f1[arr1[i]] 增加 1
- for i，范围从 0 到 arr2 的长度
- f2[arr2[i]] 增加 1
- for i，范围从 0 到 arr3 的长度
- f3[arr3[i]] 增加 1
- 对于 i = 1 至 2000，
- 如果 f1[i] 且 f2[i] 和 f3[i] 相等，则
- 将 i 插入到 res 数组中
- 如果 f1[i] 且 f2[i] 和 f3[i] 相等，则
- return res
示例
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
vector <int> ans;
unordered_map <int,int> f1,f2,f3;
for(int i =0;i<arr1.size();i++){
f1[arr1[i]]++;
}
for(int i =0;i<arr2.size();i++){
f2[arr2[i]]++;
}
for(int i =0;i<arr3.size();i++){
f3[arr3[i]]++;
}
for(int i =1;i<=2000;i++){
if(f1[i] && f2[i] && f3[i])ans.push_back(i);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {1,2,5,7,9};
vector<int> v3 = {1,3,4,5,8};
print_vector(ob.arraysIntersection(v1, v2, v3));
}
输入
[1,2,3,4,5] [1,2,5,7,9] [1,3,4,5,8]
输出
[1,5]
