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的情况，依旧如此，所以至此，证明了中位数是最优策略
题解：
代码语言：javascript复制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
}提交结果：
