求两个数组的交集c++
时间: 2023-09-04 08:15:07 浏览: 84
假设有两个数组a和b,可以用以下方法求它们的交集c:
1.先将两个数组排序,可以使用排序算法如快速排序、归并排序等;
2.设置两个指针i和j,分别指向数组a和数组b的开头;
3.将i和j所指向的元素进行比较,如果相等,则将该元素加入到交集c中,并将两个指针都向后移动一位;如果不相等,则将指向较小元素的指针向后移动一位;
4.重复步骤3,直到i或j到达数组的尾部。
下面是一个示例代码:
```python
def intersection(a, b):
a.sort()
b.sort()
i, j = 0, 0
c = []
while i < len(a) and j < len(b):
if a[i] == b[j]:
c.append(a[i])
i += 1
j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return c
```
该函数接受两个参数a和b,返回它们的交集c。该函数的时间复杂度为O(nlogn),其中n为两个数组的总长度。
相关问题
用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++实现)
在C++中,可以使用多种数据结构和算法来找到两个整数数组的交集。最常见的一种方法是利用哈希集合(如STL中的unordered_set),因为插入和查找操作的时间复杂度都是O(1),这将大大简化我们的程序。
以下是一个简单的C++函数,它接受两个整数数组作为输入,并返回它们的交集:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
std::vector<int> intersect(const std::vector<int>& arr1, const std::vector<int>& arr2) {
std::unordered_set<int> set(arr1.begin(), arr1.end());
std::vector<int> intersection;
for (const int& num : arr2) {
if (set.find(num) != set.end()) {
intersection.push_back(num);
set.erase(num); // 避免重复添加
}
}
return intersection;
}
int main() {
std::vector<int> array1 = {1, 2, 2, 1, 3};
std::vector<int> array2 = {4, 5, 2};
std::vector<int> result = intersect(array1, array2);
if (!result.empty()) {
std::cout << "Intersection of the arrays is: ";
for (int i : result) {
std::cout << i << " ";
}
} else {
std::cout << "The arrays have no common elements.\n";
}
return 0;
}
```
这个函数首先创建一个只包含arr1元素的哈希集合,然后遍历arr2,如果发现某个元素也在哈希集合中,就将其添加到结果向量`intersection`中并从集合中删除,避免重复。最后返回结果向量。
阅读全文