JavaScriptでソート済み配列から重複要素を削除する方法

ここでは、ソート済みのリテラル配列が与えられた状況を想定します。求められているのは、配列内のすべての重複をその場（in-place）で削除し、各要素が一度だけ出現するようにしたうえで、新しい配列の長さを返す関数を作成することです。

制約条件

この問題には重要な条件があります。それは、別の配列用に余分な領域を確保してはならないという点です。つまり、O(1)の追加メモリしか使わず、入力された配列そのものを直接変更する形で処理を実装する必要があります。

コード例

実際のコードは以下のようになります。

const arr = [1, 3, 3, 6, 7, 7, 9, 11, 13];
const removeDuplicates = (arr = []) => {
    let i = 0;
    while(i < arr.length - 1){
        let j = i + 1;
        if(arr[i] === arr[j]){
            arr.splice(j, 1);
        }else{
            i++;
        }
    };
};
removeDuplicates(arr);
console.log(arr);

仕組みの解説

このアルゴリズムのポイントは以下の通りです。

• インデックスiとその次のj = i + 1にある要素を比較します。
• 両者が等しい場合、配列はソート済みなので重複と判断でき、splice()メソッドでj番目の要素を削除します。
• 異なる場合はiを進めて次のペアの比較に移ります。

隣接する要素同士の比較だけで済むのは、配列があらかじめソートされているためです。これにより、追加の配列を一切使わずに重複だけを取り除くことができます。なお、新しい長さを返したい場合は、ループ終了後にreturn arr.length;を追加すれば対応できます。

実行結果

コンソールに出力される結果は以下の通りです。

[
    1, 3, 6, 7,
    9, 11, 13
]