462. 最少移动次数使数组元素相等 II : 经典贪心运用题

站长

2023年09月16日 18:58 · 阅读数 22

题目描述

这是 LeetCode 上的 462. 最少移动次数使数组元素相等 II ，难度为简单。

Tag : 「数学」

给你一个长度为 nnn 的整数数组 numsnumsnums，返回使所有数组元素相等需要的最少移动数。

在一步操作中，你可以使数组中的一个元素加 111 或者减 111 。

示例 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.lengthn == nums.lengthn==nums.length
1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
−109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109

数学

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

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

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

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

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

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

代码：

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(nlog⁡n)O(n\log{n})O(nlogn)
空间复杂度：O(log⁡n)O(\log{n})O(logn)

最后

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

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

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

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