JavaScriptで配列の要素をユニークにする最小操作回数を求める方法

本記事では、数値の配列を受け取り、すべての要素をユニーク（重複なし）にするために必要な最小の操作回数を求める JavaScript のアルゴリズムを解説します。

問題概要

数値の配列 arr を最初の引数として受け取る JavaScript 関数を作成します。

ここで「1回の操作」とは、配列内の任意の要素 arr[i] を選んで 1 増やす（インクリメントする）ことを指します。関数は、配列内のすべての値をユニークにするために必要な最小の操作回数を返す必要があります。

例えば、次の入力が与えられたとします。

const arr = [12, 15, 7, 15];

この場合の出力は次のようになります。

const output = 1;

出力の解説

配列には 15 が 2 つ含まれています。どちらか一方の 15 を 16 に 1 だけ増やせば、配列内のすべての要素がユニークになります。これ以上少ない操作で目的を達成することはできないため、答えは 1 となります。

実装コード

この問題を解くコードは以下の通りです。

const arr = [12, 15, 7, 15];
const makeUnique = (arr = []) => {
    arr.sort((a, b) => a - b);
    let count = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] <= arr[i - 1]) {
            const temp = arr[i];
            arr[i] = arr[i - 1] + 1;
            count += arr[i] - temp;
        }
    }
    return count;
};
console.log(makeUnique(arr));

コードの解説

このアルゴリズムは貪欲法（グリーディ法）に基づいており、以下の手順で動作します。

1. 配列を昇順にソートする

arr.sort((a, b) => a - b) により配列を昇順に並べ替えます。ソートしておくことで、重複や順序の逆転は必ず隣接する要素間で発生するため、一度の走査ですべて検出できます。

2. 隣接要素を比較して値を引き上げる

先頭から順に各要素 arr[i] を確認し、直前の要素 arr[i - 1] 以下であれば、arr[i - 1] + 1 まで値を引き上げます。これにより、その時点で最小限の増加量だけで重複を解消できます。

3. 操作回数を累積する

値を引き上げた量（元の値との差分）を count に加算していき、最終的な count が最小操作回数となります。

計算量

ソートに O(n log n)、その後の走査に O(n) かかるため、全体の計算量は O(n log n) です。空間計算量は入力配列をそのまま利用するため O(1)（ソートを除く）で済みます。

出力結果

上記のコードをコンソールで実行すると、次の結果が出力されます。

1

このように、ソートと貪欲法を組み合わせることで、配列をユニークにするための最小操作回数を効率的に求められます。