LeetCode453-Minimum Moves to Equal Array Elements

题目

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[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]

分析

乍一看感觉毫无思路。然而show tag以后意识到这道题应该是用数学公式推导解决的,那么我们就来推导下。现在我们不妨设数组长度为length,初始数组和为sum,初始数组最小值为min,需要移动的次数为move,最终收敛到的值为target,显然我们很容易得到下面的公式:\[sum + move \times (n – 1) = target \times length\]再仔细挖掘一件事情就离成功不远了,想一想收敛值target应该是非常不好求的一项了,那move呢?它和target之间有没有什么关系?我们在给length – 1项加1的时候,其实至始至终每次都参与了加法运算的,是从初始数组开始,值最小的那个数,倘若它不加,而去给除它外的其余数加,那么他离收敛值的距离将越来越远,需要的步数也必然增多,而反之,如果每次都把这个最小值给捎带上,由其余数之间去轮换下台,那么最后就一定能保证一个数先到达target且其他数均为targe – 1,最终就必定能保证最小步数。因此move其实就是初始最小值min到收敛值target的距离:\[move = target – min\]综合上面两个式子,我们便可以得出如下公式计算最少移动次数:\[move = sum – min \times length\]

代码

public class Solution {
    public int minMoves(int[] nums) {
        int sum = 0;
        int min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            min = nums[i] < min ? nums[i] : min;
        }
        
        return sum - min * nums.length;
    }
}

Leave a Comment.