ソート済み配列から一度だけ出現する最初の要素を見つける方法 - JavaScript

問題の概要

次のような、昇順にソートされた数値の配列があるとします。

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

この配列を受け取り、「一度だけ出現する最初の数値」を返すJavaScript関数を作成します。該当する数値が配列内に存在しない場合は、false を返します。

上記の配列の場合、期待される出力は 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));

コードの解説

このアルゴリズムは、配列がすでにソートされているという特徴を活かしています。同じ値は必ず隣接して並ぶため、隣り合う要素同士を比較するだけで重複を判定できます。

具体的には、ブール値の変数 appeared を使って「直前の要素が重複していたかどうか」を追跡します。

• 隣接する要素が同じ場合は appeared を true にして次へ進みます。
• appeared が true の状態で隣の要素と値が異なれば、重複グループが終わったことを意味するため、フラグをリセットします。
• 重複していない要素に到達した時点で、その値を即座に返します。

ループが最後まで完了しても該当する要素が見つからなければ、false を返します。この方法なら配列を一度走査するだけで済むため、計算量は O(n) と非常に効率的です。

出力

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

6