JavaScriptでソート済み配列の最初の一意な要素を見つける方法

この記事では、ソート済みの配列の中から「最初に一度だけ現れる要素」を見つけるJavaScript関数の実装方法を解説します。

問題の概要

たとえば、次のようなリテラルで構成されたソート済み配列があるとします。

const arr = [2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9];

ここで求められるのは、このような配列を受け取り、配列内で一度だけ出現する最初の数値を返すJavaScript関数を作成することです。

もし該当する数値が配列に存在しない場合は、falseを返す必要があります。

上記の配列の場合、期待される出力は 6 です。2、3、5はそれぞれ複数回出現しているため対象外となり、最初に一度だけ現れるのが6だからです。

実装例

この処理を実現するコードは以下のとおりです。

const arr = [2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9];

const firstNonDuplicate = arr => {
    let appeared = false;
    for(let i = 0; i < arr.length; i++){
        if(appeared){
            if(arr[i+1] !== arr[i]){
                appeared = false;
            };
        }else{
            if(arr[i+1] === arr[i]){
                appeared = true;
                continue;
            };
            return arr[i];
        };
    };
    return false;
};
console.log(firstNonDuplicate(arr));

出力結果

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

6

コードの解説

このアルゴリズムの最大のポイントは、配列がすでにソートされていることを活かしている点です。同じ値は必ず隣接して並んでいるため、隣り合う要素を比較するだけで重複を検出できます。

• appearedフラグ： 直前の要素が重複していたかどうかを記録するブール値です。
• 重複グループの開始を検出： 現在の要素と次の要素が等しい場合、フラグを立ててその重複グループを読み飛ばします。
• 重複グループの終了を検出： フラグが立っている状態で現在の要素と次の要素が異なれば、フラグを解除して通常の判定モードへ戻ります。
• 一意な要素の発見： フラグが立っておらず、かつ次の要素とも異なる場合、その要素は一度だけ現れる要素なので即座に返します。

ループが最後まで完了しても一意な要素が見つからなかった場合は、falseを返します。計算量はO(n)で、追加のメモリもほとんど不要なため、非常に効率的なアプローチと言えます。