每日一题-最小操作次数使数组元素相等

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

• 题目
• 示例
• 解题

题目

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

输入： [1,2,3]

输出： 3

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

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

解题

笨办法解，对数组排序，每次对前n-1个元素做+1操作，当每一个元素都相等的时候，返回+1次数。

class Solution:
    def minMoves(self, nums):
        count = 0
        len_nums = len(nums)
        while True:
            nums.sort()
            if nums[0] == nums[len_nums - 1]:
                return count
            else:
                for i in range(len_nums-1):
                    nums[i] += 1
                count += 1
           

但是这样做会超出时间限制。

我们反向思维一下，每次对n-1个元素+1，就相当于对1个元素-1。

class Solution:
    def minMoves(self, nums):
        nums.sort()
        min_num = nums[0]
        count = 0
        for i in nums:
            count += i - min_num
        return count