每日一題-最小操作次數使數組元素相等

最小操作次數使數組元素相等

• 題目
• 示例
• 解題

題目

給定一個長度為 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