両方のリストのすべての要素を実際に調べずに、2 つのリストの共通要素を見つけるにはどうすればよいですか? つまり、1 つの要素をリスト全体と比較する傾向がある通常の走査方法を使用しないということです。
追加の詳細：
1.リストはソートされています
2. 2 番目のリストで最小数の要素をトラバースして、共通要素を見つけたい
1095 次
4 に答える
3
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2= new ArrayList<Integer>();
List<Integer> list3 = new ArrayList<Integer>(list2);
list3.retainAll(list1);
list3は と の共通要素のみをlist1持ちlist2ます。
これは、明らかにリストをトラバースする最適化されたライブラリ メソッドの 1 つにすぎません。
于 2012-06-21T05:29:19.797 に答える
2
注: カバーの下をトラバースします。トラバーサルなしでは実行できません
于 2012-06-21T05:27:51.843 に答える
1
最初のリストのすべての要素について、2 番目のリストを完全にトラバースしたくないということだと思います。
1 つの方法は、両方のリストを並べ替えてから、それらを同時に読み取り、不一致の場合はまたは他のイテレータに進み、一致の場合は両方に進むことです。
別の方法は、1 つのリストをソートしてから、他のリストのすべての要素をバイナリ検索することです。
于 2012-06-21T05:29:01.047 に答える
0
外側と内側のループでリストをトラバースする単純なO（n ^ 2）ソリューションではなく、O（n）ソリューションを求めているようです。
1つの方法は、リストの1つをトラバースし、その要素をハッシュテーブルに配置することです。次に、他のリストをトラバースし、要素ごとに、要素がハッシュテーブルに存在するかどうかを確認します。これはO（n）ソリューションになりますが、もちろんスペースを消費します。
于 2012-06-21T05:54:23.533 に答える