中等

问题描述

给你一个长度为 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

提示：

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

数学

中位数有这样的性质: 对于一个有限数列 $x_1, x_2, \dots, x_n$ ，数列中的所有数与中位数的绝对差之和 $f(x) = |x_1 - x| + |x_2 - x| + \dots + |x_n - x|$ 最小。

证明：

不妨设数列是有序的，且 $x_1 \le x_2 \le \dots \le x_n$

1. 当 $n = 1$ 时，显然中位数 $x_1$ 满足性质。
2. 当 $n = 2$ 时，设 $x_1 \ne x_2$ （$x_1 = x_2$ 显然满足性质），若满足函数 $f(x) = |x_1 - x| + |x_2 - x|$ 值最小
   • 当 $x = x_1$ 或 $x = x_2$ 时，$f(x) = x_2 - x_1$
   • 当 $x < x_1$ 时，$f(x) = |x_1 - x| + |x_2 - x| = (x_1 - x) + x_2 - x_1 + (x_1 - x) = x_2 - x_1 + 2 \times (x_1 - x) \gt x_2 - x_1$
   • 当 $x > x_2$ 时，同理可得 $f(x) > x_2 - x_1$
   • 综上，中位数 $x_1$ 和 $x_2$ 满足性质
3. 当 $n > 2$ 时，根据上面的证明可知，对于区间 $[x_1,x+n]$ 满足条件的数必然在区间 $[x_1,x+n]$ 中，同理，对于区间 $[x_2,x_{n-1}]$ 满足条件的数也必然在区间 $[x_2,x_{n-1}]$，显然最终可得到满足条件必然是区间中部的数，即中位数。

因此命题成立。

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
  nums.sort((a, b) => a - b)
  let ans = 0
  let x = nums[~~(nums.length / 2)]
  for (const num of nums) {
    ans += Math.abs(num - x)
  }
  return ans
}

• 时间复杂度：$O(n \, log \, n )$
• 空间复杂度：$O(1)$

证明过程可以看到，当 $n = 2$ 时，$f(x) = x_2 - x_1$，与 $x$ 是多少其实没有关系。显然，局部的最小值的累加必然是整体的最小值，因此也可以使用双指针

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
  nums.sort((a, b) => a - b)
  let l = 0
  let r = nums.length - 1
  let ans = 0
  while (l < r) {
    ans += nums[r--] - nums[l++]
  }
  return ans
}

• 时间复杂度：$O(n \, log \, n )$
• 空间复杂度：$O(1)$