求两个集合的交集可以通过多种方法实现,下面我将介绍几种常见的方法,并提供相应的代码示例。
方法一:排序加双指针
这是一种简单且高效的方法,首先对两个集合进行排序,然后使用双指针技术找到交集。
```cpp
include include include std::vector std::sort(nums1.begin(), nums1.end()); std::sort(nums2.begin(), nums2.end()); std::vector int i = 0, j = 0; while (i < nums1.size() && j < nums2.size()) { if (nums1[i] == nums2[j]) { // 保证加入元素的唯一性 if (result.empty() || result.back() != nums1[i]) { result.push_back(nums1[i]); } i++; j++; } else if (nums1[i] < nums2[j]) { i++; } else { j++; } } return result; } int main() { std::vector std::vector std::vector for (int num : result) { std::cout << num << " "; } return 0; } ``` 方法二:使用集合 如果你使用的是Python,可以直接利用集合(set)的操作来求交集。 ```python def intersection(nums1, nums2): return list(set(nums1) & set(nums2)) nums1 = [1, 2, 2, 1] nums2 = [2, 2] result = intersection(nums1, nums2) print(result) ``` 方法三:冒泡排序法 这种方法通过冒泡排序的思想来找到交集,虽然简单,但效率不高。 ```cpp include include std::vector std::vector int k = 0; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { if (nums1[i] == nums2[j]) { result.push_back(nums1[i]); k++; break; // 避免重复添加相同的元素 } } } return result; } int main() { std::vector std::vector std::vector for (int num : result) { std::cout << num << " "; } return 0; } ``` 总结 以上是几种求交集的方法,你可以根据具体需求和数据规模选择合适的方法。排序加双指针方法在时间和空间复杂度上都有较好的表现,而使用集合的方法则更为简洁。冒泡排序法虽然简单,但在处理大数据集时效率较低。