最小移动到等数组元素

Question

给定大小为n的非空整数数组，找到使所有数组元素相等所需的最小移动次数，其中移动将n-1个元素递增1。

例：

输入：[1,2,3]

输出：3

说明：只需要三个动作（记住每个动作增加两个元素）：

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]讨论

我试图暴力破解它，但我无法使用正确的算法，循环不变量是不正确的。有人会解释它，以便我可以提高我的算法技能吗？

bool checkEquality(vector<int> &num)
{

    for (int j = 1; j < num.size(); j++)
    {
        if (num[j] != num[j - 1])
        {
            return false;
        }
    }
    return true;
}


    int main() {

        vector<int> num = { 1, 2,3 };

        int numMoves = num.size() - 1;
        int prev = 0;
        int j = 0;
        while(!checkEquality(num))
        { 
            for (int i = prev; i < num.size(); i++)
            {
                for ( j = i; j < numMoves; j++)
                {
                    num[j]++;

                }
                if (i == num.size())
                {
                    prev = j;
                    j = 0;

                }
                else
                prev = 0;
            }

        }
    }

Answer 1

您可以将问题视为减少元素，而不是使用一个元素增加其他元素。

现在问题要简单得多。你只需要添加每个元素，直到它到达数组中的最大元素。我将解决它如下：

int findMax(vector<int> &num)
{
    int maximum=num[0];
    for(int i=1;i<num.size();i++)
    {
        if(maximum<num[i])
            maximum=num[i];
    }
    return maximum;
}

int main()
{
    vector<int> num;
    num.push_back(1);
    num.push_back(2);
    num.push_back(3);

    int max_val=findMax(num);

    int answer=0;
    for(int i=0;i<num.size();i++)
    {
        answer+=max_val-num[i];
    }
    cout<<answer<<endl;

}

Answer 2

首先，你不需要为这个问题做蛮力。有一个线性时间解决方案，答案是

sum(num) - min(num) * length(num)

Edit

Explanation

除了一个之外的所有增量相当于减少那一个。所以让我们这样做吧。有多少单元素减量使所有相等？没有必要降低到当前最小值以下，那么有多少单元素递减使所有都等于当前最小值？只需将当前存在的（总和）与我们想要的（最小的n倍）区分开来。

这是C ++代码

int minMoves(vector<int>& nums) {
    if(nums.empty()) return 0;
    int n = nums.size();
    int sum = 0;
    int Min = INT_MAX;
    for(int i = 0; i < n; ++i) {
        sum += nums[i];
        Min = min(Min, nums[i]);
    }
    return (sum - Min * n);
}

甚至在一行中：

return accumulate(nums.begin(), nums.end(), 0) - nums.size() * *min_element(nums.begin(), nums.end());

Answer 3

一个简单的方法：

    int minMoves(vector<int>& nums) 
    {
         sort(nums.begin(), nums.end());
         int moves=0, n=nums.size();                   
         for(int i=0; i<n; i++)
         {
            moves += (nums[n-1-i] - nums[0]);
         }
         return moves;  
    }