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

https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii/

解法一：

求最小的moves,但并没有求最终移动到哪个数上,因为最小moves可能对应多个最终的数.假设一对数a,b( a < b )最终要移动到c , 则a,b最小的总moves为:

(c-a) + (b-c) = b-a

即当( a < c < b )时, a,b的总moves是一个常量,与c无关.(画数轴图便知)

先将所有数排序.设共有n个数.

1. 若n为奇,则数组中的中位数只有一个,记为c,由中位数的性质,a1 <= a2 <= ... <= an <= c <= bn <= ... <= b2 <= b1. (ai,bi分别是中位数c左右两侧的数,且一一对应).由上面的结论可知,最终移到中位数c,总moves最小(c不用移动).

2. 若n为偶,有两个中位数c1, c2,即 a1 <= a2 <= ... <= an <= c1 <= c2 <= bn <= ... <= b2 <= b1为了使总moves最小,最终的数c必然在两个中位数c1,c2之间.取这个区间内任意的整数即可,总moves最小.

3. 以上两种情况,总moves都为(b1-a1) + (b2-a2) + ... + (bn-an)

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        nums.sort()
        for i in range(n//2):   #0到中位数
            res += nums[n-1-i] - nums[i]
        return res