java - 私の場合、セットとリストを比較します

Question

がありますList<Integer>。このリストには重複した要素が含まれています:

//myList content is something like e.g. 1,2,1,3,3,6,7,...
List<Integer> myList = getNumbers();

また、Set<String>ご存知のように、Set一意の要素のみが含まれており、重複した要素は含まれていません。MySet<String>には String-type-in​​teger が含まれています。

//The Set content is String type integer , e.g. "1", "3", "5" …
Set<String> mySet = getNumSet(); 

と比較mySetして、持っているが持っていない要素を見つけ出し、それらの要素を から削除しmyListたいと思います。mySetmyListmySet

私が今行っている方法は、次のようにネストされた反復を使用することです。

for(Integer i : myList){
   for(String s : mySet){
         if(!myList.contains(Integer.valueOf(s))){
               mySet.remove(s);
         }
    }   

}

私よりも効率的な方法はありますか？

Answer 1

最も簡単な方法はCollection#retainAll(Collection<?> c)、コレクションの型の機能を最適化して実装できる which を使用することです。

mySet.retainAll(myList)

ただしmySet、 andは and でmyListなければなりませSet<X>んList<X>。の宣言を変更して のmySetようなもので埋めてから、メソッドInteger#valueOf(String s)を使用することをお勧めしますretainAll。

Answer 2

1. セットをコピーします。
2. リストを反復処理し、見つかったアイテムをコピーから削除します。
3. 元のセットからコピーを差し引きます。

セットにm個の要素があり、リストにn 個の要素があるとします。

次に、セットからアイテムを削除するのはO(log m)であり、リストを反復処理するのはO(n)です。全体的な複雑さはO(n × log m)です。減算は最大でO(m × log m)であるため、全体的な複雑さはO(s × log s)で、s = max(m, n)です。

アルゴリズムの複雑さはO(n ² × (log m) ² )です。

1. リスト ( O(n) ) と各項目を反復処理します。
2. セットを反復処理 ( O(log m) )、
3. リスト（O(n)）で対応するアイテムを見つけ、最後に
4. 必要に応じてセットから削除します ( O(log m) )。

Answer 3

実際には、最良のアプローチを見つけるには、より多くの情報が必要です。

myList.size() >> mySet.size() の場合、Oswald の解決策に従うか、

1. 文字列の新しいセットを作成します。
2. myList の各項目について、それが mySet にない場合は、newSet に保存します。
3. mySet.removeAll(newSet) を呼び出します。

mySet.size() >> myList.size() の場合、最善の解決策は、myList を新しい文字列のセットに変換してから、mySet.retainAll メソッドを呼び出すことです。