LeetCode刷题【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 整数

凑合公式分析

分析一下，比如

假定最小值1，即使是有相同值的情况下，也认为第一个1是最小值
1 1 3 2
2 2 3 3
3 3 4 3
4 4 4 4

或者
1 2 2 2
2 3 3 2
3 4 3 3
4 4 4 4

可以看到最小值每次都要移动

1. 假定最终停下来的位置为target,最小值为min,移动次数为steps
2. 可以知道min + steps = target
3. 另外还有一个条件，每次移动n - 1，也就是nums.length - 1个
4. 最终状态下SUM( target - nums[i] ) = ( nums.length - 1 ) * steps 左边是每个数字移动的次数之和，右边也是总和
5. 愉快的求解方程时间，二元一次方程，带入消除，基本数学操作
6. 开始求解方程nums.length * target - SUM(nums) = (nums.length - 1) * steps，左边等价于现在这样，类似求面积那种
7. 继续换算，把之前的target带入得到
   nums.length * ( min + steps ) - SUM( nums ) = ( nums.length - 1 ) * steps
8. 两边同时减去相同的部分num.length * steps得到这样的方程
   nums.length * min - SUM(nums) = - steps
9. 翻转一下steps = SUM(nums) - nums.length * min;

class Solution {
    public int minMoves(int[] nums) {
        //target 最终停下来的值
        //min 最小值
        //steps 移动次数
        //min + steps = target
        //SUM(target - nums[i]) = (nums.length - 1) * steps
        //num.length * target - SUM(nums) = (nums.length - 1) * steps
        //num.length * ( min + steps) - SUM(nums) = (nums.length - 1) * steps
        //nums.length * min - SUM(nums) = - steps
        //steps = SUM(nums) - nums.length * min;




        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int num : nums){
            min = Math.min(min,num);
            sum += num;
        }
        return sum - nums.length * min;
    }
}