2

これは、今後のテストのための私の練習問題からの質問です。私はこの問題のより効率的な解決策を見つけるのに助けを得たいと思っていました。今のところ、3つの単純なforループを使用するだけでこのタイプの問題を解決できることはわかっていますが、それはそうなるでしょうO(N^3)。

さらに、どういうわけか二分探索を組み込むことが最善の方法であると私は信じており、O(log n)私が探している答えを私に与えてくれます。残念ながら、私はちょっと立ち往生しています。

三者集合の互いに素の問題は次のように定義されます。A、B、Cの3つの集合の項目が与えられた場合、3つの集合すべてに共通の要素がない場合、つまり、次のようなxが存在しない場合、それらは三者素です。 xはA、B、およびCにあります。

A、B、およびCは、注文可能なアイテムのセット（整数）であると想定します。さらに、 O（n log n）時間でn個の整数をソートできると仮定します。O（n log n）アルゴリズムを与えて、集合が3方向集合が互いに素であるかどうかを判断します。

助けてくれてありがとう

4

3 に答える 3

5

質問文は、問題を解決する方法についての明白なヒントを与えています。3つのセットが数学的なセットであると仮定すると（要素は各セット内で一意です）、3つのセットを混ぜ合わせて並べ替え、リストを直線的にトラバースして、同じアイテムのインスタンスが3つあるかどうかを検索します。時間計算量は、ソートによって支配されO(n log n)ます。補助スペースの複雑さはせいぜいO(n)です。

別の解決策は、ハッシュベースのマップ/辞書を使用することです。3セットにわたるアイテムの頻度を数えるだけです。いずれかのアイテムの頻度が3に等しい場合（これは、更新のために頻度を取得するときに確認できます）、3つのセットは3方向に素ではありません。挿入、アクセス、および変更は、O(1)償却された複雑さで実行できるため、時間計算量はO(n)です。スペースの複雑さもO(n)です。

于 2013-03-04T05:56:51.443 に答える
2

複雑さが制約である場合（そしてスペースも定数項も制約がない場合）、これはO（n）で解くことができます。2つのビットマップを作成し、Aから最初の整数とBから2番目の整数をマッピングします。次に、使い果たされるまで3番目（C）をトラバースするか、bitmapA（testInt）とbitmapB（testInt）の両方が設定されているエントリを見つけます。

于 2013-03-04T02:22:31.313 に答える
1

この問題はo（n）で解決できます。これは、Setデータ構造を使用し、初期容量と負荷率を考慮に入れると可能になります。

public static boolean checkThreeWaySetDisjointness(Set<Integer> a, Set<Integer> b, Set<Integer> c)
    {
        int capacity = Math.round((a.size() + b.size()) / 0.75f) + 1;
        Set<Integer> container = new HashSet<Integer>(capacity);
        container.addAll(a);
        for (int element : b)
        {
            if (!container.add(element))
            {
                if (c.contains(element))
                {
                    return false;
                }
            }
        }
        return true;
    }

新しいSetコンテナを作成しているのは、既存のSet a / b / cのいずれかに直接追加を開始すると、実際のサイズの75％の容量に達すると、内部でjavaが新しいハッシュセットを作成し、既存のSet全体をコピーするためです。このオーバーヘッドはO（n）の複雑さを持ちます。したがって、ここでは、コピーのオーバーヘッドが発生しないことを保証するサイズ容量の新しいHashSetを作成しています。次に、セットa全体をコピーしてから、セットbから要素を1つずつ追加します。Javaでは、add（）がfalseを返す場合、要素が現在のコレクションにすでに存在することを意味します。はいの場合は、3番目のセットcで同じことを確認してください。HashSetのメソッドaddおよびcontainsはO（1）の複雑さを持っているため、このコード全体はO（n）で実行されます。

于 2017-12-24T07:17:50.670 に答える