462. Minimum Moves to Equal Array Elements II (Medium)

更新于 阅读次数： 本文字数： 619 阅读时长 ≈ 1 分钟

你有一个数组，允许你每次操作将任意一个元素的值 +1 或 -1，求最少需要多少操作次数让数组中的所有元素相等。

数学法

题目要求我们用最少的步数将数组元素修正到全部相等，换句话来说就是需要找到一个合适的目标，将其他数补上差值修正到与这个数相等，答案就是这些差值的和。

题目的难点在于如何意识到我们要寻找的目标是数组的中位数。

我们可以准备一个数组，首先将其排序，思考一下第一个数和最后一个数修正到目标数需要的步数。

我们会发现，第一个数和最后一个数中间的任何数都符合要求，因为最少步数实际上就是第一个数和最后一个数的差值。

我们进一步发现需要确认合适的目标，我们还需要继续确认第二个数和倒数第二个数修正到目标需要的步数。

我们重复这个过程，最终会有两种情况。

  • 如果数组的长度为奇数：最后找到的唯一一个数就是目标值；
  • 如果数组的长度为偶数：最后找到的一对数之间的任何值都是目标值，也包括这对数本身。

再仔细想想，我们在寻找的其实就是数组的中位数。现在算法浮出水面了。

  • 方便起见我们将数组进行排序；
  • 根据长度找到数组中位数的值，不用考虑太多，直接取长度除以 2 的整数值；
  • 计算所有元素与目标的差的绝对值，进行求和。
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        m = nums[len(nums) >> 1]
        ans = 0
        for i in nums:
            ans += abs(i - m)
        return ans
相关文章