【Java】配列内で奇数回出現する数値を見つけるプログラム

配列の中から奇数回出現する数値を見つけるのは、アルゴリズム学習やコーディング面接でもよく登場する定番の課題です。Javaでは、二重ループを使って各要素の出現回数を数えることで、シンプルに実装できます。ここでは、実際に動作するサンプルコードとその詳しい解説を紹介します。

サンプルコード

public class Demo {
    static int odd_occurs(int my_arr[], int arr_size){
        int i;
        for (i = 0; i < arr_size; i++){
            int count = 0;
            for (int j = 0; j < arr_size; j++){
                if (my_arr[i] == my_arr[j])
                    count++;
            }
            if (count % 2 != 0)
                return my_arr[i];
        }
        return -1;
    }
    public static void main(String[] args){
        int my_arr[] = new int[]{ 34, 56, 99, 34, 55, 99, 90, 11, 12, 11, 11, 34 };
        int arr_size = my_arr.length;
        System.out.println("配列内で奇数回出現している数値は");
        System.out.println(odd_occurs(my_arr, arr_size));
    }
}

実行結果

配列内で奇数回出現している数値は
34

コードの解説

まず、「Demo」という名前のクラスの中に、odd_occursというstaticメソッドが定義されています。このメソッドは、渡された整数型配列を先頭から順に走査し、それぞれの要素について配列内の全要素と比較を行いながら、出現回数をカウントしていきます。

カウントした出現回数を2で割った余りが0以外、つまり奇数回出現していた場合には、その時点で該当する要素の値を戻り値として返します。すべての要素を調べても奇数回出現する数値が見つからなかった場合は、-1を返して処理を終了します。

mainメソッドでは、あらかじめ整数型の配列my_arrを初期化し、その長さ（要素数）をarr_size変数に格納しています。続いて、配列とそのサイズを引数としてodd_occursメソッドを呼び出し、取得した結果をコンソールに出力します。この例では34が3回出現しているため、先頭から走査して最初に条件を満たす「34」が出力されます。

計算量に関する補足

このアプローチは非常に分かりやすい一方で、全要素同士を比較するため時間計算量はO(n²)となります。扱うデータ量が大きいケースでは、HashMapなどを利用して出現回数を一括集計する手法（時間計算量O(n)）に置き換えることで、より効率的な処理が可能になります。