これは、今後のテストのための私の練習問題からの質問です。私はこの問題のより効率的な解決策を見つけるのに助けを得たいと思っていました。今のところ、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方向集合が互いに素であるかどうかを判断します。
助けてくれてありがとう