面试题：C++ set 并集操作的性能优化

Question

已知有两个非常大的`std::set`集合`setA`和`setB`，请用C++ 高效地实现它们的并集操作，将结果存储在`resultSet`中。除了实现基本功能外，还要考虑如何优化时间复杂度和空间复杂度，阐述你的优化思路并实现代码。

Answer 1

优化思路

1. 时间复杂度优化：
   • std::set内部是基于红黑树实现的，查找操作的时间复杂度为$O(\log n)$。
   • 遍历两个std::set，对于每个元素进行查找和插入操作。如果直接对每个元素都在结果集中查找是否已存在，总时间复杂度将是$O((m + n)\log(m + n))$，其中$m$和$n$分别是setA和setB的大小。
   • 为了优化，我们可以利用std::set的有序性。先将较小的set中的元素全部插入到结果集中，然后遍历较大的set，对于每个元素，利用lower_bound函数查找是否已存在于结果集中，如果不存在则插入。这样时间复杂度可以优化到$O(m\log m + n\log m)$，假设$m \leq n$。
2. 空间复杂度优化：
   • 直接创建一个新的std::set来存储结果集，空间复杂度为$O(m + n)$。这里没有更优的通用方法来降低空间复杂度，因为并集结果集的大小理论上就是两个集合元素数量之和（去除重复后的）。

代码实现

#include <iostream>
#include <set>

void unionOfSets(std::set<int>& setA, std::set<int>& setB, std::set<int>& resultSet) {
    if (setA.size() > setB.size()) {
        // 确保setA是较小的集合
        std::swap(setA, setB);
    }

    // 将较小集合的元素插入结果集
    for (int num : setA) {
        resultSet.insert(num);
    }

    // 遍历较大集合，插入不在结果集中的元素
    for (int num : setB) {
        auto it = resultSet.lower_bound(num);
        if (it == resultSet.end() || *it != num) {
            resultSet.insert(num);
        }
    }
}

你可以使用以下方式调用这个函数：

int main() {
    std::set<int> setA = {1, 3, 5};
    std::set<int> setB = {3, 5, 7};
    std::set<int> resultSet;
    unionOfSets(setA, setB, resultSet);

    // 输出结果集
    for (int num : resultSet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}