求两个数组的交集c++
时间: 2023-12-24 14:03:22 浏览: 21
我们可以使用哈希表来实现。首先将其中一个数组中的元素存储到哈希表中,然后遍历另一个数组,如果该元素在哈希表中存在,则将其加入到交集中。时间复杂度为O(m+n),空间复杂度为O(min(m,n))。
代码实现如下:
```
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> hash;
vector<int> res;
for (int num : nums1) {
hash.insert(num);
}
for (int num : nums2) {
if (hash.count(num)) {
res.push_back(num);
hash.erase(num);
}
}
return res;
}
```
相关问题
用c++实现求两个数组的交集
```c
#include <stdio.h>
void intersection(int array1[], int size1, int array2[], int size2);
int main() {
int array1[] = {1, 2, 3, 4, 5};
int array2[] = {3, 4, 5, 6, 7};
int size1 = sizeof(array1) / sizeof(array1[0]);
int size2 = sizeof(array2) / sizeof(array2[0]);
intersection(array1, size1, array2, size2);
return 0;
}
void intersection(int array1[], int size1, int array2[], int size2) {
int i, j;
printf("Intersection of the two arrays: ");
for (i = 0; i < size1; i++) {
for (j = 0; j < size2; j++) {
if (array1[i] == array2[j]) {
printf("%d ", array1[i]);
break;
}
}
}
}
```
这个程序会输出:Intersection of the two arrays: 3 4 5。
c++两个数组求交集的实现算法(附完整源码)
两个数组求交集可以使用哈希表来实现。首先将第一个数组中的元素存入哈希表中,然后遍历第二个数组,判断每个元素是否在哈希表中,如果是,则将其加入结果数组中。
以下是完整的源码:
```python
def intersection(nums1, nums2):
# 将第一个数组中的元素存入哈希表
hash_table = {}
for num in nums1:
hash_table[num] = True
# 遍历第二个数组,判断每个元素是否在哈希表中
result = []
for num in nums2:
if num in hash_table:
result.append(num)
return result
# 测试
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2)) # 输出 [2, 2]
```
以上代码首先创建一个空的哈希表 hash_table,然后遍历第一个数组 nums1,将其元素存入哈希表中。然后遍历第二个数组 nums2,判断每个元素是否在哈希表中,如果是,则将其加入结果数组 result 中。最后返回结果数组 result 即为两个数组的交集。