462. 最少移动次数使数组元素相等 II

题目描述：

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。

在一步操作中，你可以使数组中的一个元素加1或者减1。

示例1：

输入：nums = [1,2,3]

输出：2

解释：

只需要两步操作（每步操作指南使一个元素加 1 或减 1）：

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

示例2：

输入：nums = [1,10,2,9]

输出：16

思路：

使用中位数即最优策略：

为了方便，我们先假设一共有2n+1个数，它们从小到大排序之后如下：

[ . . . m . . .]

此时m为中位数，左右各n个数，我们假设左边所有数变成m需要的代价是x，右边所有数变成m需要的代价是y

如果你感觉中位数不是最优策略：

我们来看看将所有数变成< m的某个数需要的代价，我们假设都变成m-a (a>0) ， 由于之前让m右侧变成m代价为y，所以右侧变成m-a需要的代价是y+(m-(m-a))·n = y+a·n ，同理，左侧变成m-a需要的代价是x-(m-(m-a))·n = x-a·n,但是别忘记了，m也是要变成m-a的，代价是m-(m-a) = a，所以总代价是x+y+a，是大于x+y的；

同理，我们看看将所有数变成>m的某个数的代价，我们假设都变成m+a (a>0),同上，可以得出，总代价是x+y+a，也是大于x+y的。

同理，推广到2n的情况，依旧如此，所以至此，证明了中位数是最优策略

题解：

func minMoves2(nums []int) int {
  sort.Ints(nums)
  mid := nums[len(nums)/2]
  count := 0
  for i := 0; i < len(nums); i++ {
    if nums[i] > mid {
      count = nums[i] - mid + count
    } else {
      count = mid - nums[i] + count
    }
  }
  return count
}

提交结果：