【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集（解题思路、流程图、代码片段）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集（解题思路、流程图、代码片段）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

When you feel like giving up, remember why you started.

当你想放弃时，请记住为什么你开始

01 | 👑 题目描述

给你两个数组，请分别求出两个数组的交集和并集

在数学中，我们可以通过交集和并集来描述两个集合之间的关系。

交集（Intersection）：指的是两个集合中共有的元素组成的集合。可以用符号 ∩ 来表示。例如，对于集合 A = {1, 2, 3} 和集合 B = {2, 3, 4} 来说，它们的交集就是 {2, 3}，因为这些元素同时存在于两个集合中。
并集（Union）：指的是将两个集合中所有的元素取并集组成一个新的集合。可以用符号 ∪ 来表示。例如，对于集合 A = {1, 2, 3} 和集合 B = {2, 3, 4} 来说，它们的并集就是 {1, 2, 3, 4}，因为它包含了两个集合中的所有元素，且去除了重复的元素。

换句话说，交集是寻找两个集合中相同的元素，而并集则是将两个集合中所有的元素合并在一起。

02 | 🔋 解题思路

上述数学概念同样适用于数组。当我们要找到两个数组的交集时，我们需要找到它们共有的元素。而当我们要找到两个数组的并集时，我们需要将它们中所有的元素合并在一起，并去除重复的元素。

交集

具体解题思路如下：

首先，定义两个数组A和B，分别表示待求交集的数组。
创建一个空的集合（set）或者哈希集合（unordered_set），用于存储交集的结果。集合是一种数据结构，它只会存储不重复的元素。
遍历数组A中的每个元素，将其添加到集合中。
遍历数组B中的每个元素，判断该元素是否存在于集合中。如果存在，则说明它是交集的一个元素，将其添加到另一个集合（结果集合）中。
最后，将结果集合中的元素转存到数组中，得到最终的交集数组。

【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集（解题思路、流程图、代码片段）

时间 && 空间复杂度
- 时间复杂度：
  - 遍历数组A，将元素添加到集合中：O(n)，其中n是数组A的大小。
  - 遍历数组B，判断元素是否存在于集合中，并将交集元素添加到结果集合中：O(m)，其中m是数组B的大小。
  所以，总体的时间复杂度为O(n + m)，我们可以将其简化为O(max(n, m))，其中max(n, m)表示两个数组中较大的大小。
- 空间复杂度：
  - 使用一个集合来存储数组A中的元素：O(n)，其中n是数组A的大小。
  - 使用一个结果集合来存储交集元素：最坏情况下，结果集合的大小为min(n, m)，其中n和m分别是数组A和数组B的大小。
  所以，总体的空间复杂度为O(n + min(n, m))，我们可以将其简化为O(max(n, m))，其中max(n, m)表示两个数组中较大的大小。

并集

具体的解题流程：
1. 首先，定义两个数组A和B，分别表示待求并集的数组。
2. 创建一个空的集合（set）或者哈希集合（unordered_set），用于存储并集的结果。集合是一种数据结构，它只会存储不重复的元素。
3. 遍历数组A中的每个元素，将其添加到集合中。
4. 遍历数组B中的每个元素，判断该元素是否存在于集合中。如果不存在，则说明它是并集的一个元素，将其添加到集合中。
5. 最后，将集合中的元素转存到数组中，得到最终的并集数组。

【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集（解题思路、流程图、代码片段）

时间 && 空间复杂度
- 时间复杂度
  将数组A中的元素插入集合：O(n)，其中n是数组A的大小。
  遍历数组B，并将元素插入集合：O(m)，其中m是数组B的大小。
  因此，总体的时间复杂度为O(n + m)，我们可以将其简化为O(max(n, m))，其中max(n, m)表示两个数组中较大的大小
- 空间复杂度
  创建一个集合来存储并集的结果：O(n + min(n, m))，其中n和m分别是数组A和数组B的大小。在最坏情况下，如果两个数组没有重复元素，集合的大小为n + m。
  创建一个数组来存储集合中的元素：O(n + min(n, m))，与创建集合的过程相同。
  所以，总体的空间复杂度为O(n + min(n, m))，我们可以将其简化为O(max(n, m))，其中max(n, m)表示两个数组中较大的大小
  因此，整个算法的

03 | 🧢 代码片段

交集

#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> intersection(std::vector<int>& A, std::vector<int>& B) {
    std::unordered_set<int> setA(A.begin(), A.end()); // 将数组A中的元素放入集合
    std::unordered_set<int> resultSet;
    
    for (int num : B) {
        if (setA.count(num) > 0) { // 判断num是否存在于集合setA中
            resultSet.insert(num); // 将num添加到结果集合中
        }
    }
    
    std::vector<int> result(resultSet.begin(), resultSet.end()); // 将结果集合转存到数组中
    return result;
}

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {4, 5, 6, 7, 8};
    
    std::vector<int> result = intersection(A, B);
    
    std::cout << "Intersection: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集（解题思路、流程图、代码片段）

并集

#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> unionSet(std::vector<int>& A, std::vector<int>& B) {
    std::unordered_set<int> resultSet(A.begin(), A.end()); // 将数组A中的元素放入集合

    for (int num : B) {
        resultSet.insert(num); // 将数组B中的元素添加到集合中
    }
    
    std::vector<int> result(resultSet.begin(), resultSet.end()); // 将集合转存到数组中
    return result;
}

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {4, 5, 6, 7, 8};
    
    std::vector<int> result = unionSet(A, B);
    
    std::cout << "Union Set: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}