C++で配列の要素をすべて一意にするための最小増加操作回数を求める方法

問題の概要

整数の配列 A が与えられます。ここでいう「1回の操作」とは、任意の A[i] を選び、その値を 1 だけ増やすことです。この操作を繰り返して、配列 A のすべての値を一意(重複なし)にするために必要な最小の操作回数を求めます。

例えば、入力が [3,2,1,2,1,7] の場合、出力は 6 になります。6 回の操作を行うと、配列は [3,4,1,2,5,7] となり、すべての値が異なる状態にできます。一方、5 回以下の操作ではすべての値を一意にすることができないことが示せます。

解法のアプローチ

この問題は、ソートと貪欲法(グリーディ法)を組み合わせることで効率的に解くことができます。手順は以下のとおりです。

• 答えを格納する変数 ret を 0 で初期化します。
• 配列 A を昇順にソートします。
• i を 1 から配列 A のサイズ - 1 までループします。
• もし A[i] が A[i-1] 以下であれば、ret に (A[i-1] + 1) - A[i] を加算し、A[i] を A[i-1] + 1 に更新します。
• 最後に ret を返します。

この方法のポイントは、ソート済みの配列に対して隣接する要素同士を比較することで、重複を検出できる点にあります。A[i] が直前の要素以下の場合、A[i] を「直前の要素 + 1」まで増やす必要があり、その増分がそのまま操作回数として ret に加算されます。ソートによって配列が昇順に並んでいるため、この処理を左から右へ一度行うだけで、全体の最小操作回数が求まります。

実装例

より理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minIncrementForUnique(vector<int>& A) {
        int ret = 0;
        sort(A.begin(), A.end());
        for(int i = 1; i < A.size(); i++){
            if(A[i] <= A[i - 1]){
                ret += (A[i - 1] + 1) - A[i];
                A[i] = A[i - 1] + 1;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {3,2,1,2,1,7};
    Solution ob;
    cout << (ob.minIncrementForUnique(v1));
}

入力

[3,2,1,2,1,7]

出力

6

計算量の分析

• 時間計算量: O(n log n) — 配列のソートが支配的であり、その後の走査は O(n) で完了します。
• 空間計算量: O(1) — ソートをインプレースで行う場合、追加のメモリは定数個の変数のみで済みます。

このように、ソートと隣接要素の比較というシンプルな発想により、すべての要素を一意にするための最小操作回数を効率よく求めることができます。