453.最小操作次数使数组元素相等

最小操作次数使数组元素相等

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1：

输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
示例 2：

输入：nums = [1,1,1]
输出：0

提示：

n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
答案保证符合 32-bit 整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1

正向思考的过程。假设m为操作次数，x为最后的相等的结果，则sum + m * (n-1) = x * n，方程中多了一个未知的变量，也就是最后的值x，接下来也是最重要的部分了，x = min_val + m，也就是每次增加时最小值都必须包含在内。我们还是从正向的角度来看，最后要如何才能使得所有的结果相等。首先是将数组中的最大值排除在外，最小值带着其余的值不断增加，知道最小值和最大值相等(抹平和最大值之间的差);现在最小值和第二个大的值之间的差并没有被抹平，但是最大值和最小值是相等的，现在是把原先第二大的值排除在外，其余的数值增加，抹平最小值和第二大的数值之间的差值；现在是第三个大的值和最小值之间的差值没有被抹平，所以第三个最大值被排除在外，其余数值不断增大直到最小值和第三个大的值相等，不断进行下去抹平最小值和其余值之间的差距。
其实使得最后结果相等的过程就是使得最小值抹平和其余值之间的差值，首先是选择一个和最小值不相等的值，将其排除在外，不断增大最小值，直到两者相等，抹平差值，再选择下一个和最小值不等的，将其排除在外，不断增大最小值，直到两者相等，抹平差值，并不断进行下去，抹平最小值和每个数之间的差距。其实从这里来看，就有m = \(\sum_{i=0}^{n}(nums[i] - min\_val)\)。
不过只是为了说明x = min_val + m,代入得到m = sum - min_val * n.

code1

class Solution {
public:
    //每次操作会使n-1个数增加1
    //求最小操作次数使得元素数目相等
    
    //数学题：假设操作次数为m,初始和为sum,最后的值为x
    //sum + m * (n-1) = n * x
    //还差最后的数值x未知
    //脑筋急转弯：x = m + min_val
    //最小值必然每次都会被增加

    //m = sum - min_val * n

    int minMoves(vector<int>& nums) {
        
        long long int min_val = nums[0];
        long long int sum = 0;
        for(auto item : nums)
        {
            sum += item; 
            if(item < min_val) min_val = item;
        }

        return sum - min_val * nums.size();
    }
};

解题思路2

逆向思维，最后都是为了抹平差距，n-1个数加上1相当于1个数减去1，最后相等的结果就是所有数都等于最小值，也是可以得到正向推导中的公式：m = \(\sum_{i=0}^{n}(nums[i] - min\_val)\)。

code

class Solution {
public:
    //逆向思维
    //n-1个元素增加1
    //相当于一个元素减少1
    //所有元素都减少到最小值则相等

    int minMoves(vector<int>& nums) {
        int min_val = nums[0];

        for(auto item : nums) if(item < min_val) min_val = item;
    
        int ans = 0;
        for(auto item : nums) ans += item - min_val;

        return ans;
    }
};