繰り返しのある2つの配列の交差

Question

2つの配列の繰り返しを繰り返すメソッドを作成しようとしています。

例：{1,2,5,4,1,3} and {1,2,1} -> {1,1,2}.

私が交差点を行いますが、繰り返しのない方法を持っています。私はArrays.*またはList.*を使用せずに繰り返しを追加することができますどのように

public int[] findSameElements(int[] p1, int[] p2) { 
    int count = 0; 
    for (int i = 0; i < p1.length; i++) { 
     for (int j = 0; j < p2.length; j++) { 
     if (p1[i] == p2[j]) { 
      count++; 
      break; 
     } 
     } 
    } 

    int[] result = new int[count]; 
    count = 0; 
    for (int i = 0; i < p1.length; i++) { 
     for (int j = 0; j < p2.length; j++) { 
     if (p1[i] == p2[j]) { 
      result[count++] = p1[i]; 
      break; 
     } 
     } 
    } 

    return result; 
    } 

？

Answer 1

は、次の関数試してください：あなたはまた、並べ替え適用すべき必要な場合

public int[] findSameElements(int[] p1, int[] p2) 
{ 
    int count = 0; 
    bool[] choosen = new bool[p2.length]; 

    for (int i = 0; i < p1.length; i++) 
    { 
     for (int j = 0; j < p2.length; j++) 
     { 
      if (!choosen[j] && p1[i] == p2[j]) 
      { 
       choosen[j] = true; 
       count++; 
       break; 
      } 
     } 
    } 

    int[] result = new int[count]; 
    count = 0; 
    for (int i = 0; i < p2.length; i++) 
    { 
     if (choosen[i]) 
     { 
      result[count] = p2[i]; 
      count++; 
     } 
    } 

    return result; 
} 

を、この解決策はO（N^2）複雑さを有します。 O（NLogN）の複雑さもまた可能です。

Answer 2

あなたはhistogram（Map<Integer,Integer>として表現される）および構築することができます：ヒストグラムに

1. 挿入し、各要素eについて
2. 反復LIST2をリスト1からすべての要素（およびその繰り返しの数） ：
   - ヒストグラムは、（正の値を持つ）要素eが含まれている場合：プリント（または新しいリストに追加）E、およびヒストグラム

ノートで電子の値を減らしますこの解はO(n+m)時間（平均の場合）であり、O(min{n,m})スペースであること。

---

コードサンプル（代わりにアレイのList<T>を使用して - それは容易もちろん変更することができる）は：

private static <T> Map<T,Integer> populateHistogram(List<T> list) { 
    Map<T,Integer> histogram = new HashMap<T, Integer>(); 
    for (T e : list) { 
     Integer val = histogram.get(e); 
     histogram.put(e, val == null ? 1 : val+1); 
    } 
    return histogram; 
} 
public static <T> List<T> generateInterectionList(List<T> list,Map<T,Integer> histogram) { 
    List<T> res = new ArrayList<T>(); 
    for (T e : list) { 
     Integer val = histogram.get(e); 
     if (val != null && val > 0) { 
      res.add(e); 
      histogram.put(e,val - 1); 
     } 
    } 
    return res; 
} 
public static <T> List<T> getIntersection(List<T> list1, List<T> list2) { 
    Map<T,Integer> histogram = populateHistogram(list1.size() > list2.size() ? list2 : list1); 
    return generateInterectionList(list1.size() > list2.size() ? list2 : list1,histogram); 
} 
public static void main(String[]args){ 
    List<Integer> list1 = Arrays.asList(new Integer[]{1,2,5,4,1,3}); 
    List<Integer> list2 = Arrays.asList(new Integer[]{1,2,1}); 
    System.out.println(getIntersection(list1, list2)); 
} 

---

注意それはまた、O(nlogn)時間とO(logn)で行うことができます（ソートアルゴリズムのスタックトレースのために）リストをソートした後、リストごとに1つのポインタを並列に反復する。

擬似コード：一方

繰り返しI1 < list1.lengthとi2 < list2.length：

1. 場合LIST1 [I1] == LIST2 [I2]：
   - 印刷LIST1 [I1 ]
   - リスト1 [i1の場合、I1を増やし、他I2
2. ]>リスト2 [I2]：
   - 他
3. I2を増やす：
   - 増加i1

Answer 3

コレクションを使用しない理由はありますか？ retainAll(...)方法は、あなたが欲しいものを行います。

List<Integer> list1 = ... 
List<Integer> list2 = ... 
List<Integer> intersection = list1.retainAll(list2); 

Answer 4

ハッシュテーブルを使用する方法の1つです。 2つの配列から2つの別々のハッシュテーブルを作成します。キーの値のペアは（要素、カウント）です。次に、より小さいハッシュテーブルに進み、count_min = min（テーブルaの要素の数、テーブルbの要素の数）の各要素count_min回数を出力します。これは、追加の空間の複雑さを伴う線形アルゴリズムである。

空間複雑度= O（n + m）ここで、nとmは2つの配列のサイズです。 時間複合体O（n）ここでn> m。