LeetCode：453. Minimum Moves to Equal Array Elements

- 日理万妓 2022-09-02 12:55 122阅读 0赞

# 453. Minimum Moves to Equal Array Elements #

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]

**翻译**：

给定一个大小为`size`的数组`nums`，每次你需要对它的“除最大值以外”的值进行`+1`操作，当数组中所有值都一样时结束。问：经过多少次可以达到平衡

# 思路 #

我们先来观察一组数据：

通过观察这组数据，可以发现：

*  经过  ( 11 − 7 ) × 1 = 4 (11-7) \\times 1=4 (11−7)×1=4 次后，最后两位数可以达到平衡
 *  经过  ( 7 − 3 ) × 2 = 8 (7-3) \\times 2 =8 (7−3)×2=8 次后，最后三位可以达到平衡，因为第二位每次加1，需要后两位交替2次
 *  经过  ( 3 − 1 ) × 3 = 6 (3-1)\\times 3=6 (3−1)×3=6 次后，最后四位（全部）可以达到平衡，最后第第一位每加1，需要后面三位交替3次

经过总结，可以得到如下公式：

设  nums有序，且  nums = \[ x 1 , x 2 , x 3 , ⋯   , x n \] \\text\{设~~nums有序，且~~nums\} = \[ x\_1,x\_2,x\_3, \\cdots , x\_n\] 设  nums有序，且  nums=\[x1,x2,x3,⋯,xn\]

则，总次数为  
 T = ( x n − x n − 1 ) × 1 + ( x n − 1 − x n − 2 ) × 2 + ⋯ + ( x 2 − x 1 ) × ( n − 1 ) = x n + x n − 1 + … ⋯ + x 2 − x 1 ( n − 1 ) = x n + x n − 1 + … ⋯ + x 2 + x 1 − x 1 n \\begin\{aligned\} \\\\\\\\ T&=(x\_n-x\_\{n-1\})\\times 1 +(x\_\{n-1\} - x\_\{n-2\})\\times2 + \\cdots +(x\_2-x\_1)\\times (n-1) \\\\\\\\ &= x\_\{n\}+x\_\{n-1\}+\\ldots \\cdots+x\_\{2\}-x\_\{1\}(n-1) \\\\\\\\ & =x\_\{n\}+x\_\{n-1\}+\\ldots \\cdots+x\_\{2\} + x\_1 - x\_\{1\}n \\end\{aligned\} T=(xn−xn−1)×1\+(xn−1−xn−2)×2\+⋯\+(x2−x1)×(n−1)=xn\+xn−1\+…⋯\+x2−x1(n−1)=xn\+xn−1\+…⋯\+x2\+x1−x1n

将测试数据代入该公式，为：  
 T = 11 + 7 + 3 + 1 − 1 × 4 = 18 T = 11+7+3 + 1 - 1\\times 4 = 18 T=11\+7\+3\+1−1×4=18

# 上代码 #

class Solution:
        def minMoves(self, nums) -> int:
    		return sum(nums) - len(nums)*min(nums)