453. 最小移动次数使数组元素相等

问题描述

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。

 

示例:

输入:
[1,2,3]

输出:
3

解释:
只需要3次移动（注意每次移动会增加两个元素的值）：

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

解题思路

一直将最小数移动到与最大数相同即可。

如对于 \([1,2,3,4]\):

1. \([\boxed{1},2,3,\boxed{4}]\to[\boxed{2},3,4,\boxed{4}]\to[\boxed{3},4,5,\boxed{4}]\to[\boxed{4},5,6,\boxed{4}]\) 共移动 \(4-1=3\) 次
2. \([\boxed{4},5,\boxed{6},4]\to[\boxed{5},6,\boxed{6},5]\to[\boxed{6},7,\boxed{6},6]\) 共移动 \(6-4=3-1=2\) 次
3. \([\boxed{6},\boxed{7},6,6]\to[\boxed{7},\boxed{7},7,7]\) 共移动 \(7-6=2-1\) 次

所以移动的总次数为 \(\sum_{i=0}^{n-1}(\text{nums}[i]-\min(\text{nums}))\)

---

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        m = min(nums)
        return sum((x - m for x in nums))

返回顶部

在手机上阅读