java - 繰り返しのある 2 つの配列の交点

Question

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

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

交差はしますが、繰り返しはありません。

  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;
  }

Arrays.*またはを使用せずに繰り返しを追加するにはどうすればよいList.*ですか?

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

ヒストグラム( として表されますMap<Integer,Integer>)を作成し、次のことを行うことができます。

1. list1 からヒストグラムにすべての要素 (およびその繰り返し数) を挿入します。
2. 各要素 e に対して list2 を繰り返し
   ます。

このソリューションは、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));
}

---

リストをソートし、リストごとに1つのポインターを使用して並列に反復することで、O(nlogn)時間と空間で（ソートアルゴリズムのスタックトレース用）実行することもできることに注意してくださいO(logn)

擬似コード:

i1 < list1.length および i2 < list2.length の間、繰り返します。

1. if list1[i1] == list2[i2]:
   - list1[i1] を出力
   - i1,i2 を増やす
2. else if list1[i1] > list2[i2]:
   - i2 を増やす
3. それ以外:
   - i1 を増やす

Answer 3

そのための1つの方法は、ハッシュテーブルを使用することです。2つの配列から2つの別々のハッシュテーブルを作成します。キーと値のペアは（element、count）です。次に、小さいハッシュテーブルを調べて、各要素count_minをcount_min = min（テーブルaの要素の数、テーブルbの要素の数）の回数だけ出力します。これは、スペースがさらに複雑になる線形アルゴリズムです。

スペースの複雑さ=O（n + m）ここで、nとmは2つの配列のサイズです。時間の複雑さO（n）ここで、n>m。

Answer 4

コレクションを使用しない理由はありますか? retainAll(...)メソッドはあなたが望むことをします：

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