462.最少移动次数使数组元素相等II
462.最少移动次数使数组元素相等II
题解
题目：让所有数组元素变成相等的数字，一次只能加一或减一，问需要几次
思路：
- 需要找到一个数字，计算元素到该数字的距离即可
- 如何求这个数字呢？
设x在区间[a0,a1,a2,a3,a4,…,an]外，对于a0和an来说，ans=a0-x + an -x
设x在区间[a0,a1,a2,a3,a4,…,an]内，对于a0和an来说，ans=an-a0
那么肯定在区间内，比区间外的步数小。
同理不断扩大a0,缩小an,最终这个x就是数组排序后的中位数
代码
func minMoves2(nums []int) int { sort.Ints(nums) l, r := 0, len(nums)-1 ans := 0 for l < r { ans += nums[r] - nums[l] l++ r-- } return ans } func minMoves2(nums []int) int { sort.Ints(nums) mid := 0 if len(nums)%2 == 0 { mid = (nums[len(nums)/2-1] + nums[len(nums)/2]) / 2 } else { mid = nums[len(nums)/2] } ans := 0 for _, v := range nums { ans += abs(v - mid) } return ans } func abs(i int) int { if i > 0 { return i } return -i }
