n個のセット間の最大交点

Question

それぞれにy個の要素（ソートされていない整数）を持つx個のセットがあります。私はこのセットの対の間の交差の最大サイズを見つけたいと思う。

* 5セット、サイズ1 = 3

セット：4

：2セット1

例えば

セット3：5 6 7

セット5：

4セット5 10 11

最大の交差点を設定2で1を設定し、それのサイズが2できました。 答えは2です。

したがって、私はHashSetsを使ってO（x^2 * y）ですべてのペアを探し出し、交差のサイズを計算するだけです。しかし、私はそれをもっと速くしたい。私は、特定のアルゴリズムやデータ構造が役に立つと思う。あなたは私にいくつか考えを与えることができますか？

更新日：xとyは約10^3です。要素はintです。そして、等しいセットはありません。

Answer 1

私が考えることができる1つの最適化は、最初のセットと残りの部分との間の交差サイズを記憶しておき、いくつかのケースを切断するためにデータを使用することです。

あなたはそれを使用するにはどうすればよい：

：あなたがセット A、 B、長さ nの Cとあなたのケースではセットの場合

intersection(A,B) = p 
intersection(A,C) = q 

その後、

intersection(B,C) <= n - abs(p - q) 

をお持ちの場合は

を

S0 = { 1 2 3 } 
S1 = { 4 2 3 } 
S2 = { 5 6 7 } 

あなたがintersection(S0,S1) = 2を計算し、結果を覚えている：そして

[ i(0,1)=2 ] 

intersection(S0,S2) = 0、そう

[ i(0,1)=2; i(0,2)=0 ] 

そして、あなたが最初の要素

(S1[0]=4 != S2[0]=5) 

を比較した後intersection(S1,S2)を計算するとき、あなたがいることを言うことができますintersection(S1,S2) <= 2これは最高の結果ですあなたはこれまでのところ持っています。

さらに改善できる点は、より正確な交差の結果を覚えていても、それらのすべてを計算していないことです。

これが最善の選択肢かどうかはわかりません。たぶん、これとはまったく異なるアプローチが存在するでしょう。ここで

Answer 2

は、いくつかの擬似コードです：だから

function max_intersection(vector<vector<int>> sets): 
    hashmap<int, vector<set_id>> val_map; 
    foreach set_id:set in sets: 
     foreach val in set: 
      val_map[val].push_back(set_id); 
    max_count = 0 
    vector<int> counts = vector<int>(size = sets.size() * sets.size(), init_value = 0); 
    foreach val:set_ids in val_map: 
     foreach id_1:set_id_1 in set_ids: 
      foreach id_2:set_id_2 in set_ids where id_2 > id_1: 
       count = ++counts[set_id_1 * sets.size() + set_id_2]; 
       if (count > max_count): 
        max_count = count; 
    return max_count; 

XがセットとYの数である場合は、各セットの要素数れる：

1. val_mapへの挿入がO(X*Y)
2. の作成ですcountsであり、各要素をゼロに初期化することは、O(X^2)
3. 交差点がない場合（各値は正確に1回発生します）、最後のループは時刻O(X*Y)で実行されます。しかし、他の極端な場合、交差点が多数ある場合（すべてのセットが同等）、最後のループはO(X^2*Y)で実行されます。

したがって、交差の量に応じて、時間の複雑さはO(X*Y + X^2)とO(X^2*Y)の間です。

Answer 3

私はO(x*x*y)を改善するソリューションを考えることはできませんが、私はハッシュを回避する方法を提案することができ、代わりに期待複雑O(x*x*y)の10^6追加メモリのコストで複雑O(x*x*y)を持っています。あなたが与えた制約を見ると、あなたは10^6以下の異なる数しか持たないでしょう。だから、私の考えは次の通りです。すべての数字を並べ替えて一意にする（重複を取り除く）。各番号に1から10^6までの一意の番号（または一意の番号の番号）を割り当てます（並べ替えられた配列と一意の配列でその順序を使用します）。その後、各ペアのハッシュマップオンの代わりに、サイズが10^6のビットセットを使用します。あなたはO(x*x*y)という特定の複雑さを持っています（私が提案する事前計算は、O(x * y *(log(x) + log (y))の複雑さです）。