Java で配列に重複要素があるかどうかをチェックする方法

はじめに

この実験では、Java で配列に重複する要素があるかどうかを異なるアプローチでチェックする方法を学びます。まず、ネストされたループを使用した基本的な方法から始め、比較プロセスを明確に理解できるようにします。

次に、HashSet データ構造を利用したより効率的な手法を探索し、Java コレクションを活用してより高速に重複を検出する方法を示します。最後に、配列をソートすることで重複の識別プロセスを簡素化できる方法を調べます。この実験の終わりまでに、Java 配列の重複要素を処理するための複数の戦略を身につけることができるようになります。

ネストされたループを使って重複要素を検出する

このステップでは、Java でネストされたループを使用して配列内の重複要素を見つける基本的なアプローチを探索します。この方法は直感的で理解しやすいため、配列操作と基本的なアルゴリズム設計の学習の良い出発点となります。

まず、~/project ディレクトリに FindDuplicatesNested.java という名前の新しい Java ファイルを作成しましょう。WebIDE のファイルエクスプローラーで project フォルダを右クリックし、「新しいファイル」を選択して名前を入力することで直接作成できます。

次に、コードエディターで FindDuplicatesNested.java ファイルを開き、以下の Java コードを追加します。

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

このコードを分解して説明しましょう。

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};：この行は numbers という名前の整数配列を宣言し、重複要素を含むいくつかの値で初期化します。
• for (int i = 0; i < numbers.length; i++)：これは外側のループです。インデックス i を使用して配列の各要素を反復処理します。
• for (int j = i + 1; j < numbers.length; j++)：これは内側のループです。インデックス i の各要素に対して、インデックス i の次の要素から始まる配列の「残りの」要素を反復処理します。これは、要素を自身と比較することを避け、同じ重複要素のペアを 2 回見つけることを避けるために重要です（例えば、インデックス 1 とインデックス 4 を比較し、その後インデックス 4 とインデックス 1 を比較することを避けます）。
• if (numbers[i] == numbers[j])：この条件は、インデックス i の要素がインデックス j の要素と等しいかどうかをチェックします。もし等しければ、重複要素を見つけたことになります。
• System.out.println("Duplicate found: " + numbers[j]);：重複要素が見つかった場合、この行は重複要素を示すメッセージを出力します。

Ctrl + S（macOS では Cmd + S）を押してファイルを保存します。

次に、WebIDE の下部にあるターミナルを開きます。~/project ディレクトリにいることを確認してください。pwd と入力して Enter キーを押すことで確認できます。出力は /home/labex/project である必要があります。

javac コマンドを使用して Java コードをコンパイルします。

javac FindDuplicatesNested.java

エラーがなければ、コンパイルは成功し、~/project ディレクトリに FindDuplicatesNested.class ファイルが作成されます。ls と入力して Enter キーを押すことで確認できます。

最後に、java コマンドを使用してコンパイルされた Java プログラムを実行します。

java FindDuplicatesNested

プログラムによって見つかった重複要素を示す出力が表示されるはずです。

このネストされたループのアプローチは、配列内のすべての可能な要素のペアを比較することで機能します。理解しやすい一方で、非常に大きな配列に対しては非効率になる可能性があります。次のステップでは、重複要素を見つけるより効率的な方法を探索します。

HashSet を使用した効率的な重複チェック

前のステップでは、ネストされたループを使用して重複要素を見つけました。この方法は簡単ですが、大きな配列に対しては低速になる可能性があります。このステップでは、HashSet を使用して重複要素を見つけるより効率的な方法を学びます。

HashSet は、Java のコレクションで、一意の要素を格納します。つまり、すでに HashSet に存在する要素を追加しようとすると、追加操作は失敗します（正確には、false を返します）。この特性を利用して、効率的に重複を検出することができます。

考え方は次の通りです。配列を反復処理し、各要素について HashSet に追加しようとします。add() メソッドが false を返す場合、その要素はすでにセットに存在するため、重複要素であることを意味します。

~/project ディレクトリに FindDuplicatesHashSet.java という名前の新しい Java ファイルを作成しましょう。

コードエディターで FindDuplicatesHashSet.java ファイルを開き、以下の Java コードを追加します。

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

このコードの新しい部分を見てみましょう。

• import java.util.HashSet; と import java.util.Set;：これらの行は、HashSet を使用するために必要なクラスをインポートします。
• Set<Integer> uniqueElements = new HashSet<>();：この行は、Integer オブジェクトを格納する空の HashSet を作成します。HashSet は Set インターフェースを実装しているため、Set を型として使用します。
• for (int number : numbers)：これは拡張 for ループ（for-each ループとも呼ばれます）で、numbers 配列の各要素を反復処理する便利な方法です。
• !uniqueElements.add(number)：これが核心のロジックです。uniqueElements.add(number) は、現在の number を HashSet に追加しようとします。もしその数値がすでに存在する場合、add() は false を返します。! 演算子はこの結果を反転させるため、add() が false を返した場合のみ if 条件が真になり、重複要素であることを示します。

ファイルを保存します（Ctrl + S または Cmd + S）。

次に、ターミナルで Java コードをコンパイルします。

javac FindDuplicatesHashSet.java

コンパイルが成功したら、プログラムを実行します。

java FindDuplicatesHashSet

HashSet メソッドを使用して見つかった重複要素が一覧表示された出力が表示されるはずです。このメソッドは、特に大きな配列に対して、ネストされたループのアプローチよりも一般的に高速です。なぜなら、HashSet への要素の追加と要素のチェックは非常に効率的だからです。

ソート済み配列でテストする

この最後のステップでは、特に配列がソートされている場合に重複要素を見つける別のアプローチを探索します。配列がソートされている場合、重複要素は常に隣り合っています。これにより、隣接する要素を比較するだけで、非常に簡単かつ効率的に重複要素を見つけることができます。

まず、~/project ディレクトリに FindDuplicatesSorted.java という名前の新しい Java ファイルを作成しましょう。

コードエディターで FindDuplicatesSorted.java ファイルを開き、以下の Java コードを追加します。

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

このコードの重要な部分を見てみましょう。

• import java.util.Arrays;：この行は、配列に関するユーティリティメソッド（ソートを含む）を提供する Arrays クラスをインポートします。
• Arrays.sort(numbers);：この行は、numbers 配列を昇順にソートします。
• for (int i = 0; i < numbers.length - 1; i++)：このループは、ソートされた配列を反復処理します。現在の要素 (numbers[i]) と次の要素 (numbers[i + 1]) を比較するため、numbers.length - 1 までループします。
• if (numbers[i] == numbers[i + 1])：この条件は、現在の要素が次の要素と等しいかどうかをチェックします。もし同じであれば、重複要素を見つけたことになります。

ファイルを保存します（Ctrl + S または Cmd + S）。

次に、ターミナルで Java コードをコンパイルします。

javac FindDuplicatesSorted.java

コンパイルが成功したら、プログラムを実行します。

java FindDuplicatesSorted

見つかった重複要素が一覧表示された出力が表示されるはずです。配列がソートされているため、出力では重複要素が連続して表示されます。

この方法は、ソートされた配列に対して非常に効率的です。ソート後に配列を 1 回だけ走査するだけで済みます。ただし、最初のソートステップ自体には時間コストがかかり、それは Arrays.sort() が使用するソートアルゴリズムに依存します。int のようなプリミティブ型の場合、Java の Arrays.sort() はデュアルピボットクイックソートを使用し、平均的な時間計算量は O(n log n) です。

これで、Java で配列内の重複要素を見つける 3 つの異なる方法を探索しました。ネストされたループを使用する方法、HashSet を使用する方法、ソートされた配列を使用する方法です。各方法には、単純さ、効率性、要件（配列がソートされているなど）の面でトレードオフがあります。これらの異なるアプローチを理解することは、与えられた問題に最適な方法を選択するために重要です。

まとめ

この実験では、Java で配列に重複要素が含まれているかどうかをチェックするさまざまな方法を探索しました。まず、ネストされたループを使用したシンプルなアプローチを実装しました。この方法では、配列内の各要素を他のすべての要素と比較します。この方法は理解しやすいですが、時間計算量が O(n^2) となり、大きな配列に対しては効率が低くなります。

次に、より効率的な重複チェックのために HashSet データ構造を活用する方法を学びました。配列を反復処理し、各要素を HashSet に追加しようとすることで、要素がすでに存在する場合に HashSet の add() メソッドが false を返すため、迅速に重複要素を判断できます。このアプローチは、平均して通常 O(n) の時間計算量を提供し、大幅に改善されています。最後に、配列を最初にソートすることでも重複要素を効率的に見つけることができることを考えました。ソート後は重複要素が隣り合うためです。