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

题目描述

这是 LeetCode 上的 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

提示：

• $n == nums.length$
• $1 <= nums.length <= 10^5$
• $-10^9 <= nums[i] <= 10^9$

---

数学

假定所有的 $nums[i]$ 均位于数轴上的 $nums[i]$ 的位置，题目要求我们在数轴上找出一个点 $t$，使得所有 $nums[i]$ 到 $t$ 的距离之和最小。

首先，容易证明 $t$ 不可能位于最小的 $nums[i]$ 的左侧，也不可能位于最大的 $nums[i]$ 的右侧，否则我们「至少」能够将目标点调整为 最小的 $nums[i]$ 或 最大的 $nums[i]$ 来得到更小的距离总和。

其实由上述这一点进行推广，已经可以证明最优点必然是在中间点（$nums$ 数量为奇数时）或者中间两点形成的闭区间中的任意点（$nums$ 数量为偶数时）。
但为了证明更加直观，我们仍从「反证法」的角度进行证明。

我们根据每个 $nums[i]$ 位于 $t$ 的左侧还是右侧进行划分：假设位于 $t$ 左侧的 $nums[i]$ 对答案的贡献为 $A$，位于 $t$ 右侧的 $nums[i]$ 对答案的贡献为 $B$，最终目的是为了让 $A + B$ 最小。

我们猜想当 $t$ 取中位数时，$A + B$ 取得最小值，并通过「反证法」进行证明：

• 假设真实最优解 $t’$ 位于中位数 $t$ 的 左侧：假设调整距离为 $d$，导致变化的点数为 $x$，则有左边总和为 $A - xd$，右边总和为 $B + (n - x)d$，总和为 $A + B - 2xd + nd$，如果要使得结果更好，需要满足 $nd - 2xd < 0$，即满足 $x > \frac{n}{2}$，这与我们本身 $t$ 为中位数，即左右两边数的个数均为 $\frac{n}{2}$ 冲突（特别地，当 $nums$ 为偶数时，且目标点位于中间两点中的任一点时，左右数的个数并非为 $\frac{n}{2}$，但距离总和情况与 $t$ 位于两点间的其余点的情况一致）；

• 假设真实最优解 $t’$ 位于中位数 $t$ 的 右侧：同理。

代码：

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, t = nums[(n - 1) / 2], ans = 0;
        for (int i : nums) ans += Math.abs(t - i);
        return ans;
    }
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.462 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。