algorithm - 从列表的映射中输出在每个其他元素列表中不相交的元素集的映射

Question

我有一个列表映射，每个列表都有整数。输出是在所有其他元素列表中不相交的元素集的映射。

例如: 下面是列表的 map

列表 1 - 1,2,3,4,5

列表 2 - 3,4,5,6,7,8

列表 3 - 1,2,3,5,6,7,8

所有列表的交集是 - 3,5 输出应为列表映射(不包括 3、5)

列表 1 - 1,2,4

列表 2 - 4,6,7,8

列表 3 - 1,2,6,7,8

我有一个使用 2 个 for 循环的解决方案，但它的复杂度为 O(n*n)。试图找到最佳解决方案。任何指针表示赞赏。

Answer 1

您可以使用哈希表表示不同的集合。这种计算整体交集的方法是 O(M)，其中 M 是所有集合中元素的总数。

然后，您需要计算原始集与计算出的交集之间的集差。同样，使用哈希表 O(K*N) 可以非常快速地完成此操作，其中 K 是整个交集中的元素数，N套数。

算法的结构将使用两个非嵌套的for循环。第一个计算所有集合的交集，第二个去除所有集合中的冗余元素。

您将在 Coliru 上找到 C++ 中的运行示例。 .

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

// Complexity: O(min(set1.size(), set2.size()))
template <typename T>
std::unordered_set<T> intersection(std::unordered_set<T> const& set1, std::unordered_set<T> const& set2) {
    if (set2.size() < set1.size()) {
        return intersection(set2, set1);
    } else {
        std::unordered_set<T> inter;
        for (auto const& el1 : set1) {
            if (std::find(set2.cbegin(), set2.cend(), el1) != set2.cend()) {
                inter.emplace(el1);
            }
        }
        return inter;
    }
}

using int_hashset = std::unordered_set<int>;

int main()
{
    std::vector<int_hashset> input_sets = {{1, 2, 3, 4, 5},
                                           {3, 4, 5, 6, 7, 8},
                                           {3, 5, 6, 7, 8}};

    auto inter_set = *input_sets.cbegin();
    // Complexity: O(number of elements)
    for (auto it = input_sets.cbegin()+1; input_sets.cend() != it; ++it) {
        inter_set = intersection(inter_set, *it);
    }
    for (auto const& i : inter_set) {
        std::cout << "Elem in overall intersection: " << i << '\n';
    }

    // O(N*inter_set.size())
    for (auto& input_set : input_sets) {
        // O(inter_set.size())
        for (auto el : inter_set) {
            input_set.erase(el);
        }
    }

    int i = 0;
    for (auto const& input_set : input_sets) {
        ++i;
        for (auto el : input_set) {
            std::cout << "Element in set " << i << ": " << el << '\n';
        }
    }
    return 0;
}

注意:这是分摊的复杂性。如果你的集合中有很多碰撞，复杂性会增加。