力扣-453 最小操作次数使数组元素相等

题目

453 最小操作次数使数组元素相等

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

示例：

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

解

方法一、按题意进行解题，即暴力解法。

1. 对数组进行循环，找到当前的最大值和最小值所对应的数
2. 判断最大值和最小值是否相等
3. 不相等则对所有除了最大数之外的数加一
   循环上述过程直到最大值和最小是相等

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        res = 0
        min, max = 0, len(nums) - 1
        while  True:
            for i in range(len(nums) - 1):
                if nums[max] < nums[i]:
                    max = i
                if nums[min] > nums[i]:
                    min = i
            
            if nums[max] == nums[min]:
                break
            
            for i in range(len(nums) - 1):
                if i != max:
                    nums[i] += 1
            res += 1
        return res

方法二、利用排序减少每次定位最大数和最小数的时间。

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        # 对nums进行逆序排序
        nums.sort(reverse=True)
        res = 0
        for i in range(len(nums) - 1):
            res += nums[i] - nums[-1]
        return res

方法三、大神精妙解法（LeetCode：JonnyHuang）

利用数学方法解题，逻辑超级清晰，强烈推荐。

1. 假设我们最少的操作次数是,次操作后每个元素相等，相等元素设为
2. 对于整个列表的个元素都要进行加一操作那么增加的总数是
3. 原本的列表之和为,次操作后应该存在这样的关系等式：
    [最少操作次数] * [每次对个元素进行操作] + [原列表的和] = [操作后的相等元素] * 即：

这里最关键的地方是确定的值，如果我们知道了的值那么肯定就能知道,那么的值是多少呢？

答案是:中的最小值 即：

原因：对于最小值，你每次的递加都必须对原列表的最小值加1，每次操作中必须覆盖最小值， 次操作后， 最小值就变为了，该值就是最后的相同值 即公式：

公式展开变换后得k:

代码就简单了：

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        return sum(nums) - len(nums) * min(nums) if len(nums) != 1  else  0