別のリストと比較して1つのリストから重複を削除する

Question

私は2つのオブジェクトのリストを持っており、他のリストにあるリストからそのインスタンスを削除したいと思います。

私は次の2つのリストを持ち、それぞれの文字がオブジェクトを表していると仮定します。

リストLISTA = {A、B、C、D、E、F、G、H、I、J}

リストListBの= {D、G、K、P、Z}

今、明らかListBのもので、私はリスタこの

リスタ= {A、B、C、E、F、H、I、J}

できようになりたいリスタにあるD及びGを有しますあなたはO（n）またはO（n2）未満でこれを解決する方法を提案してください。

私は両方のリストを反復処理して、重複するインスタンスを比較することで削除できますが、より効率的なものを作りたいと思っています。

Answer 1

あなたはssantosは、あなたがセットを使用することができ、答えのようにlistA.removeAll(listB);

Answer 2

を試し、他から1つのリストの要素を削除するにはSet

に両方のリスト要素を追加することができます。

また、リストがソートされている場合は、そのリストを交互に繰り返すこともできます。 ListAの現在の要素よりも大きい要素に到達するまでListAを繰り返し、ListAの現在の要素より大きい要素に到達するまでListBを反復処理します。

Answer 3

リストがソートされていない場合は、 O（n）containsメソッドを持つArrayListまたは他の同様のリスト実装である場合、削除を実行するにはlistBの項目を持つHas​​hSetを作成する必要があります。アイテムがセットに入れられないと、O（n^2）のパフォーマンスになります。あなたが必要なものを行うには

最も簡単な方法は、このようです：

listA.removeAll(new HashSet(listB)); 

ArrayList.removeAll(Collection)はなぜである、（少なくとも私がチェックしたJDK 1.6と1.7のバージョンで）あなたのためのセットにアイテムを入れていないだろうあなた自身で上記のHashSetを作成する必要があります。

removeAllメソッドは、リストを削除するたびに配列の圧縮を避けるため、リストの先頭に保持する項目をコピーします。したがって、渡されたHashSetに対して、合理的に最適であり、O（ n）。

Answer 4

以下は、の予想時刻O(n)で解決するための擬似Cです。

lenA = length pf listA 
lenB = length of listB 
shortList = (lenA <= lenB) ? A : B 
longList = (shortList == A) ? B : A 

create hash table hashTab with elements of shortList 

for each element e in longList: 
    is e present in hashTab: 
     remove e from longList 

now, longList contains the merged duplicate-free elements