1

配列を共通要素とマージしたい。次のような配列のリストがあります。

List<int[]> arrList = new List<int[]>
{
    new int[] { 1, 2 },
    new int[] { 3, 4, 5 },
    new int[] { 2, 7 },
    new int[] { 8, 9 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 9, 13 }
};

これらの配列を次のようにマージしたいと思います。

List<int[]> arrList2 = new List<int[]>
{
    new int[] { 1, 2, 7 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 4, 5, 8, 9, 13 } //order of elements doesn't matter
};

どうやってするの？

4

3 に答える 3

3

各数値をラベル付きグラフの頂点とします。配列ごとに、指定された配列の番号が指す頂点を接続します。たとえば、与えられた配列 (1, 5, 3) は、2 つのエッジ (1, 5) と (5, 3) を作成します。次に、グラフ内のすべての連結成分を見つけます ( http://en.wikipedia.org/wiki/Connected_component_(graph_theory)を参照) 。

于 2013-09-22T13:24:22.567 に答える
1

Disjoint-Set Forest データ構造を使用します。データ構造は、次の 3 つの操作をサポートしています。

  • MakeSet(item) - 単一のアイテムで新しいセットを作成します
  • Find(item)- アイテムを指定して、セットを検索します。
  • Union(item1, item2)- 2 つのアイテムが与えられた場合、それらが属するセットを結合します。

Union各配列を調べて、最初の要素とその後にある各要素を呼び出すことができます。リスト内のすべての配列の処理が完了したら、すべての番号をもう一度調べて呼び出すことで、個々のセットを取得できFind(item)ます。同じセットを生成する番号はFind、同じ配列に入れる必要があります。

O(α(n))このアプローチは、償却された状態でマージを終了します (α非常にゆっくりと成長するため、すべての実用的な目的では、小さな定数と見なすことができます)。

于 2013-09-22T13:29:02.737 に答える