2つの整数配列間の交差
1. 概要
このクイックチュートリアルでは、2つの整数配列‘a’と‘b’の間の交差を計算する方法を見ていきます。
また、重複エントリの処理方法にも焦点を当てます。
実装には、Streamsを使用します。
2. 配列のメンバーシップ述語
2つのセットの共通部分は、定義上、1つからのすべての値を持つセットであり、これも2番目のセットの一部です。
したがって、2番目の配列のメンバーシップを決定するには、FunctionまたはPredicateが必要です。 List はこのようなメソッドをすぐに提供するため、これをListに変換します。
Predicate isContainedInB = Arrays.asList(b)::contains;
3. 交差点の構築
結果の配列を構築するために、最初のセットの要素を順番に検討し、それらが2番目の配列にも含まれているかどうかを確認します。 次に、これに基づいて新しい配列を作成します。
Stream APIは、必要なメソッドを提供します。 最初にStreamを作成し、次にmembership-Predicateでフィルタリングし、最後に新しい配列を作成します:
public static Integer[] intersectionSimple(Integer[] a, Integer[] b){
return Stream.of(a)
.filter(Arrays.asList(b)::contains)
.toArray(Integer[]::new);
}
4. 重複するエントリ
Javaの配列はSetの実装ではないため、入力と結果のエントリが重複するという問題に直面します。 結果の出現回数は、最初のパラメーターの出現回数に依存することに注意してください。
ただし、セットの場合、要素は複数回出現してはなりません。 これはdistinct()メソッドを使用してアーカイブできます:
public static Integer[] intersectionSet(Integer[] a, Integer[] b){
return Stream.of(a)
.filter(Arrays.asList(b)::contain)
.distinct()
.toArray(Integer[]::new);
}
したがって、交差の長さはパラメータの順序に依存しなくなります。
ただし、doubleエントリを削除するため、配列とそれ自体の共通部分が再び配列にならない場合があります。
5. マルチセット交差
複数の等しいエントリを許可するより一般的な概念は、マルチセットです。 それらの場合、交差は入力オカレンスの最小数によって定義されます。 したがって、メンバーシップ- Predicate は、結果に要素を追加する頻度をスコアに保持する必要があります。
これには、 remove()メソッドを使用できます。このメソッドは、メンバーシップを返し、要素を消費します。 したがって、‘b’ のすべての等しい要素が消費された後、結果に等しい要素は追加されません。
public static Integer[] intersectionSet(Integer[] a, Integer[] b){
return Stream.of(a)
.filter(new LinkedList<>(Arrays.asList(b))::remove)
.toArray(Integer[]::new);
}
配列APIは不変のリストのみを返すため、専用の可変リストを生成する必要があります。
6. 結論
この記事では、containsおよびremoveメソッドを使用して、Javaの2つの配列の交差を実装する方法を説明しました。
すべての実装、コードスニペット、およびテストは、 GitHubリポジトリにあります。これはMavenベースのプロジェクトであるため、そのままインポートして実行するのは簡単です。