最小移动到相等的数组元素

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;
            }

        }
    }

原文由 احمد 发布，翻译遵循 CC BY-SA 4.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;

}

原文由 Omid N 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

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

编辑

解释

增加除一个之外的所有值相当于减少那个。所以让我们这样做吧。多少个单元素递减才能使所有内容相等？没有必要递减到当前最小值以下，那么有多少个单元素递减量才能使全部等于当前最小值？只需将当前存在的值（总和）与我们想要的值（最小值的 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());

原文由 Kaidul 发布，翻译遵循 CC BY-SA 4.0 许可协议