JavaScriptで配列から最大の「1度だけ現れる数値」を見つける方法

本記事では、整数の配列を第1引数（かつ唯一の引数）として受け取るJavaScript関数を作成する方法を解説します。

この関数の役割は、配列を順番に走査し、その中で一度だけ出現する数値のうち最大のものを見つけ出して返すことです。もし配列内に一意な数値がひとつも存在しない場合は、-1を返す仕様とします。

前提となる制約

配列の各要素には次の制約が与えられています。つまり、すべての要素は0より大きく101未満であることが保証されています。

0 < arr[i] < 101

具体例

たとえば、入力配列が以下のような場合を考えてみましょう。

const arr = [35, 37, 33, 39, 34, 39, 38, 31];

このとき期待される出力は次の通りです。

const output = 38;

理由はシンプルです。配列内で最も大きい数値は39ですが、これは2回出現しているため候補から除外されます。したがって、一度だけ登場する数値の中で最大である38が正解となります。

アプローチ：頻度カウント配列を活用する

配列の要素が必ず0より大きく100以下であるという制約を活かせば、非常に効率的な解法が可能です。

具体的には、長さ100のカウント用配列を用意して元の配列の各数値の出現回数を記録します。その後、カウント配列を大きい側（末尾）から小さい側へ向かって走査し、最初に出現回数が1となった要素を見つければ、それが答えになります。

この手法では時間計算量がO(n)、空間計算量は定数サイズに抑えられるため、大変効率的です。

サンプルコード

const arr = [35, 37, 33, 39, 34, 39, 38, 31];
const pickGreatestUnique = (arr = [], bound = 100) => {
    const map = Array(bound).fill(0);
    for(let i = 0; i < arr.length; i++){
        const num = arr[i];
        map[num - 1]++;
    }
    for(let j = bound - 1; j >= 0; j--){
        const frequency = map[j];
        if(frequency === 1){
            return j + 1;
        }
    }
    return -1;
}
console.log(pickGreatestUnique(arr));

実行結果

このコードをコンソールで実行すると、次のように正しく出力されます。

38

まとめ

要素の範囲が限定されている場合、ハッシュマップの代わりに固定長のカウント配列を使うことで、シンプルかつ高速に「最大の一意な数値」を求められます。一意な数値が存在しないケースにも対応できるよう、最後に-1を返す処理を忘れずに入れておきましょう。