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

Question

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

例如:下面是列表的地图

清单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循环。第一个计算所有集合的交集，第二个处理所有集合中的冗余元素。

您将在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;
}

注:这是摊销复杂性。如果你在你的集合中有很多碰撞，那么它的复杂性就会上升。