每日一题(2022-05-19)——最少移动次数使数组元素相等 II

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
}

提交结果：