別の配列にある配列から要素を削除する

Question

インタビューで質問があります。

2つの配列があります。

arr1 = {3,5,6,8,1,6,7}; 
arr2 = {5,6,8}; 

ので、最終的な出力は、私がO(n^2)時間でそれに答えることができ

arr1 = {3,8,1,7}; 

です。

良い方法がありますか？二番目の配列からHashSetのを構築することにより、（N + M）時間Oでそれを行うことができ

よろしく、

のRajesh

Answer 1

ルックアップとして使用します。これらのルックアップはO（1）で実行され、セットを構築するにはO（m）が必要です。

次に、O（n）の最初の配列を反復処理し、必要な要素だけを残しておきます。

Answer 2

O(n)では、HashSetを使用してこれを行うことができます。 HashSetの中で二番目の配列要素を追加し、1回のパスで最初の配列を反復処理する - これはあなたのO（n）は、以下のJavaで

実装を提供します

。 、あなたはハッシュセットO（M）中に被除去要素は元の配列から要素を削除するかどうかを確認するために、その後、償却置くタイプミス

int[] arr2 = {5,6,8}; 
Set toBeRemoved = new HashSet<Integer>(); 
for(int i:arr2){ 
toBeRemoved.add(i); 
} 
for(int i:arr1){ 
if(toBeRemoved.contains(i)){ 
//Logic to remove from array 
//Or else if you dont have space contraint just add elements to a new array 
} 
}