C++で配列の全要素を等しくするための最小移動回数を求める方法

サイズ n の配列が与えられたとします。すべての配列要素を同じ値にするために必要な最小の移動回数を求めるのがこの問題の目的です。ここで「1回の移動」とは、n - 1 個の要素をそれぞれ 1 だけ増加させることを意味します。

例えば、入力が [3,2,3,4] の場合、出力は 4 になります。

解法のアプローチ

この問題を解く鍵となるのは、発想の転換です。「n - 1 個の要素を 1 増やす」という操作は、要素間の相対的な差に着目すると「1 個の要素を 1 減らす」操作と数学的に等価です。したがって、各要素を最小値まで減らすのに必要な操作回数、つまり「各要素と最小値の差の総和」が答えになります。

具体的には、以下の手順に従います。

• n を配列 nums のサイズとします。
• n が 0 の場合は、0 を返します。
• 配列 nums をソートします。
• ans を 0 で初期化します。
• i を 0 から n - 1 まで繰り返し、ans に nums[i] - nums[0] を加算します。
• ans を返します。

ソート後は最小値が nums[0] に位置するため、各要素と最小値の差を合計するだけで答えが求まります。計算量はソート部分が O(n log n)、合計の計算が O(n) となり、非常に効率的です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += nums[i] - nums[0];
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {3,2,3,4};
    cout << (ob.minMoves(v));
}

入力

{3,2,3,4}

出力

4

この実装では、配列 [3,2,3,4] をソートすると [2,3,3,4] となり、最小値 2 との差はそれぞれ 1、0、1、2 となります。その合計は 4 であり、期待される出力と一致します。