[数据结构与算法]算法 — 最小操作次数使数组元素相等

题目

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

示例 ：

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

解题思路:

首先，假设执行过程无误，则设数组操作前最小值为min，最大值为max，共需操作k次，操作前数组总和为sum。分析得知，每次从数组中找出最小的两个值并分别加一，则每次使 sum 加上（n-1），则执行 k 次共使 sum 加 k *（n-1），即执行结束时数组总和为 sum + k*（n-1）。从另一方面由贪心算法得知，经过 k 步后原数组最小值 min 变为 min+k，此时数组所有值均为 min+k，则数组和为 n*（min+k）。故得等式 sum+k*（n-1） = n*（min+k），化简得 k = sum-n*min，求解完成。

class Solution {
    public int minMoves(int[] nums) {
        int sum = 0 , n = nums.length , min = Integer.MAX_VALUE;
        for (int num : nums){
            sum += num;
            min = Math.min(min,num);
        }
        return sum - n * min;
    }
}