43

交点を見つける必要がある可変数の ArrayList があります。弦のセット数の現実的な上限はおそらく 35 前後ですが、それ以上になる可能性もあります。コードは必要ありません。何が効率的かについてのアイデアだけです。コーディングを開始しようとしている実装がありますが、他のアイデアを聞きたいです。

現在、私の解決策について考えてみると、漸近的な実行時間が Θ(n 2 )になるはずです。

助けてくれてありがとう！

シュレッド

編集：明確にするために、私は本当にそれを行うためのより速い方法があるか知りたいだけです. Θ(n 2 ) よりも高速です。

4

8 に答える 8

59

Set.retainAll()2 つの集合の交点を見つける方法です。を使用する場合、 s をsHashSetに変換し、それらすべてをループで使用すると、実際には O(n) になります。ArrayListSetretainAll()

于 2010-05-17T19:11:54.060 に答える
36

受け入れられた答えは問題ありません。更新として : Java 8 以降、2 つの の交点を見つけるためのわずかに効率的な方法がありますSet。

Set<String> intersection = set1.stream()
    .filter(set2::contains)
    .collect(Collectors.toSet());

それがわずかに効率的である理由は、元のアプローチではその要素を追加するset1必要があり、それらが にない場合は再度削除する必要があったためですset2。このアプローチは、必要なものを結果セットに追加するだけです。

厳密に言えば、Java 8 より前のバージョンでもこれを行うことができましたが、Streams がなければ、コードはかなり面倒でした。

両方のセットのサイズが大幅に異なる場合は、小さい方のストリーミングよりも優先されます。

于 2016-10-06T17:56:42.877 に答える
18

Google GuavaSets.intersection(set1, set2)には、2 つのセットの交点の変更不可能なビューを返す静的メソッドもあります。

于 2015-04-21T11:30:53.200 に答える
6

もう1つのアイデア-配列/セットのサイズが異なる場合、最小のものから始めるのが理にかなっています。

于 2010-05-17T19:20:13.783 に答える
3

最良のオプションは、ArrayList の代わりに HashSet を使用してこれらのリストの内容を格納することです。それができれば、交差する要素を追加する一時的な HashSet を作成できます (putAll(..) メソッドを使用します)。tempSet.retainAll(storedSet) を実行すると、tempSet に交差点が含まれます。

于 2010-05-17T19:12:31.777 に答える
0

それらを並べ替え (n lg n)、二分探索 (lg n) を実行します。

于 2010-05-17T19:10:50.910 に答える
0

単一の HashSet を使用できます。オブジェクトがすでに設定されている場合、add() メソッドは false を返します。リストからオブジェクトを追加し、偽の戻り値のカウントをマークすると、ヒストグラムのセット+データのユニオンが得られます（カウント+1がリストカウントに等しいオブジェクトが交差点です）。カウントを TreeSet に投げると、空の交差を早期に検出できます。

于 2010-05-17T20:04:10.047 に答える