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

ソート済みの配列から「一度だけ出現する最初の数値」を効率よく見つけたい場面は、実務でもよくあります。本記事では、JavaScriptを使ってソート済み配列内の最初の一意な要素を取得する方法を、具体的なコード例とともに解説します。

問題の概要

次のようなリテラル（数値）のソート済み配列が与えられたとします。

const arr = [32, 32, 63, 63, 63, 75, 75, 86, 87, 88, 89];

この配列に対して、重複していない最初の数値を返すJavaScript関数を作成します。

• 一意な数値が存在する場合は、その値を返す
• すべての要素が重複している（一意な数値が存在しない）場合は、false を返す

上記の例では、32・63・75は複数回出現しているため無視され、初めて一度だけ登場する数値は 86 です。したがって、期待される出力は 86 となります。

実装コード

以下が実際のコード例です。配列はすでにソートされているため、隣接する要素同士を比較するだけで一意な値を判定できる点がポイントです。

const arr = [32, 32, 63, 63, 63, 75, 75, 86, 87, 88, 89];

const firstUnique = 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(firstUnique(arr));

実行結果

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

86

処理の流れを解説

1. フラグ変数による重複判定

変数 appeared は、「現在注目している値が直前の値と重複していたか」を記録するフラグです。true の間は同じ値のグループの中にいると判断し、そのグループが終わるまでスキップします。

2. 隣接要素との比較だけで完結

配列が昇順にソートされているため、同一の値は必ず連続して並びます。これにより、各要素について「隣の要素と等しいか」を確認するだけよく、全要素の出現回数を数えるような追加の処理は不要になります。

3. 計算量のメリット

このアプローチは配列を先頭から一度走査するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。未ソートの配列の場合は Map やオブジェクトで出現回数を記録する方法が一般的ですが、ソート済みであることが保証されているなら、この手法が最もシンプルかつ高速です。

まとめ

ソート済み配列の特性を活かせば、隣接要素の比較だけで最初の一意な要素を線形時間で見つけられます。一意な要素が存在しないケースにも対応できるよう、最後に false を返す設計にしておくことで、実用的な関数としてそのまま利用できます。