JavaScriptで配列内の奇数回出現する要素を見つける方法

整数の配列が与えられたとき、その中で奇数回だけ出現する要素を1つ見つける関数を作成する必要があります。この問題では、奇数回出現する整数は必ず1つだけ存在することが保証されています。

解決のアプローチ

この問題は、まず配列をソートするというシンプルな戦略で解くことができます。配列を昇順に並べ替えると、同じ値を持つ要素が隣り合って並ぶようになります。そのため、その後配列を先頭から走査しながら連続する同一値の出現回数をカウントし、奇数回出現している要素を特定できます。

アルゴリズムの流れ

1. 配列を数値として正しくソートする（比較関数 (a, b) => a - b を指定）
2. 現在の要素が直前の要素と同じ場合は、カウントを1増やして次へ進む
3. 別の値に切り替わったタイミングで、直前の値の出現回数が奇数であればそれを返す
4. ループが完了しても返せていない場合は、最後に追跡していた値を返す

なお、JavaScript の sort() メソッドはデフォルトでは要素を文字列として比較するため、数値の大小関係を保つには必ず数値用の比較関数を渡す点に注意してください。

コード例

以下が実際のコードです。

const arr = [20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5];
const findOdd = arr => {
    let count = 0;
    let last;
    arr.sort((a, b) => a - b);
    for (let i = 0; i < arr.length; i++){
        if (arr[i] === last) {
            count++;
            continue;
        };
        if(count % 2){
            return last;
        };
        last = arr[i];
        count = 1;
    };
    return last;
};
console.log(findOdd(arr));

実行結果

コンソールには次のように出力されます。

この入力配列の場合、5 だけが3回（奇数回）出現しており、他のすべての値は2回ずつ現れるため、結果として 5 が返されます。

5