c++中如何求两个数组的交集_c++数组交集实现方法-C++-PHP中文网

c++中如何求两个数组的交集_c++数组交集实现方法

冰火之心

发布： 2025-10-01 20:49:01

原创

366人浏览过

答案：C++中求两数组交集常用三种方法：①排序+双指针，时间复杂度O(m log m + n log n)，适合可排序数组；②哈希表法，时间复杂度O(m + n)，无需排序且自动去重；③STL的set_intersection，仅适用于有序数组，代码简洁但可能含重复元素。

c++中如何求两个数组的交集_c++数组交集实现方法

在C++中求两个数组的交集，常见做法是利用排序和双指针，或使用哈希表来提高查找效率。以下是几种实用的实现方法，适用于不同场景。

方法一：排序 + 双指针（适合有序或可修改原数组）

如果允许对数组排序，可以先对两个数组排序，然后使用双指针遍历，找出相同的元素。

示例代码：

#include <vector>
#include <algorithm>
using namespace std;

vector<int> getIntersection(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());

    vector<int> result;
    int i = 0, j = 0;

    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            result.push_back(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

登录后复制

说明：该方法时间复杂度为 O(m log m + n log n)，空间复杂度较低。若要求去重，可在插入 result 前判断是否已存在。

方法二：哈希表（适合不允许排序或需保留原始顺序）

将一个数组的元素存入 unordered_set，再遍历另一个数组检查是否存在，能快速判断交集元素。

立即学习“C++免费学习笔记（深入）”；

集简云

软件集成平台，快速建立企业自动化与智能化

查看详情

示例代码：

#include <vector>
#include <unordered_set>
using namespace std;

vector<int> getIntersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> set1(nums1.begin(), nums1.end());
    unordered_set<int> resultSet;

    for (int num : nums2) {
        if (set1.count(num)) {
            resultSet.insert(num); // 自动去重
        }
    }

    return vector<int>(resultSet.begin(), resultSet.end());
}

登录后复制

说明：此方法时间复杂度为 O(m + n)，适合大数据量。使用 resultSet 避免重复结果。

方法三：STL 算法 set_intersection（仅适用于有序数组）

C++ 标准库提供 set_intersection 函数，可用于求两个有序序列的交集。

示例代码：

#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

vector<int> getIntersection(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());

    vector<int> result;
    set_intersection(nums1.begin(), nums1.end(),
                     nums2.begin(), nums2.end(),
                     back_inserter(result));
    return result;
}

登录后复制

说明：简洁高效，但要求输入有序，且结果可能包含重复元素（若原数组有重复），如需去重可配合 unique 使用。

基本上就这些常用方法。根据是否允许修改原数组、是否需要去重、性能要求等选择合适方案。哈希表法最通用，双指针节省内存，STL 方法代码最简洁。不复杂但容易忽略细节，比如重复元素处理。

以上就是c++++中如何求两个数组的交集_c++数组交集实现方法的详细内容，更多请关注php中文网其它相关文章！