両方の配列に属していない2つの配列から要素を表示

Question

このコードを書いて、どの配列にも属している要素を表示しました。私たちはより効率的にすることができますか？

public class App { 
public static void main(String[] args){ 
    int[] a = {1,2,3,4,5,6,7,8,9}; 
    int[] b = {1,20,3,4,15,13,6,7,8,12}; 

    for(int i = 0; i < a.length; i++){ 
     int temp = a[i]; 
     for(int j = 0; j < b.length; j++){ 
      if(b[j] == temp){ 
       b[j] = -1; 
       a[i] = -1; 
      } 
     } 
     if(a[i] != -1) 
      System.out.print(a[i] + " "); 
    } 

    for(int i = 0; i < b.length; i++){ 
     if(b[i] != -1) 
      System.out.print(b[i] + " "); 
    } 
} 
} 

Answer 1

あなたのコードはmとnは、配列のサイズですO(m * n)時間複雑で実行されます。

配列を変更することができる場合は、これを改善するためのいくつかの方法があります。

1. は、両方の配列をソートします。
2. 配列のmerge-sortのマージ操作に似た操作を行いますが、要素が等しい場合はマージ操作を行います。

全体的な複雑さ= O(m * log(m) + n * log (n) + m + n) = O(m * log(m) + n * log(n)) = O(k * log(k))ここで、k = max(m, n)です。この方法では、追加のスペースは使用されない、すなわち、空間の複雑さはO(1)であることに留意されたい。

Answer 2

はい。絶対に。 現在O(m * n)があり、mは配列aのサイズで、nは配列bのサイズです。
最初のアレイからのデータをhashset（O(n)操作、nのサイズがaの場合）にコピーします。次に、2番目の配列を解析して、データがhashset（O(1)オペレーション）にあるかどうかを確認します。
2番目の配列に対しても同様の操作を行うことを検討してください。