リストのマップから、他のすべてのリストの要素に分解された要素のセットのマップを出力します。

Question

私はリストのマップを持っています。各リストには整数があります。出力とは、他のすべての要素リストにおいて互いに素である要素のセットのマップです。 EXのために

：以下 は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

私はforループ2を用いて溶液を有するが、それはO（N * Nを有します）複雑さ。最適なソリューションを見つけようとしています。任意のポインタが高く評価されました。

Answer 1

ハッシュテーブルを使用して異なるセットを表すことができます。この方法では、交差全体を計算することはO（M）です。ここで、Mはすべてのセットの要素の合計数です。

次に、元のセットと計算された交差点との間の差異を計算する必要があります。ここでもまた、ハッシュテーブルを使用して、これは実際に高速で行われます。O（K * N）ここで、Kは全体交差の要素の数です。Nセットの数。

アルゴリズムの構造は、ネストされていない2つのforループを使用します。最初のすべてのセットの交差を計算する、2番目のすべてのセットで冗長な要素を取り除く。

C++の実行例は、Coliruにあります。

#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; 
} 

注：これは償却された複雑さです。あなたのセットの中にたくさんの衝突があると複雑さが増します。