453. Minimum Moves to Equal Array Elements

453. Minimum Moves to Equal Array Elements II

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation: Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Example 2:

Input: nums = [1,1,1]
Output: 0

Constraints:

• n == nums.length

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

• The answer is guaranteed to fit in a 32-bit integer.

My Solutions:

给一个长度为n的数组，每次可以对 n-1 个数字同时加1，问最少需要多少次这样的操作才能让数组中所有的数字相等。--> 每次给除了数组最大值的所有数字加1能快速的到达平衡状态。但是这道题如果每次找出最大值，然后给其他数字加1，再判断是否平衡，思路是正确，但是时间溢出。

换一个角度来看问题，给 n-1 个数字加1，效果等同于给那个未被选中的数字减1，比如数组 [1，2，3]，给除去最大值的其他数字加1，变为 [2，3，3]，全体减1，并不影响数字间相对差异，变为 [1，2，2]，这个结果其实就是原始数组的最大值3自减1。那么问题也可能转化为，将所有数字都减小到最小值。只要先找到最小值，然后累加每个数跟最小值之间的差值即可。

这个问题还可以转化成求出数组的数字之和 sum，然后用 sum 减去最小值和数组长度的乘积，得到的就是sum和如果全部element都是最小值的差值。这个差值就是需要移动的步数。

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