『LeetCode』462 最少移动次数使数组元素相等 II

题目

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 \leq nums.length \leq 10^5\)
\(-10^9 \leq nums[i] \leq 10^9\)

相似题目

题解

【最少移动次数使数组元素相等 II】扫描线及其数学证明

证明

容易证明最后数组中的元素必定全部变为数组中某个元素值，证明如下：

设数组元素已经排序（非递减），记为 \([x_1, x_2, \dots, x_n]\), 假设最终数组元素中全部变为 \(k\), 且对 \(\forall i, x_i \neq k\)

若 \(k \leq x_1\)，即 \(k\) 小于数组中最小的值 \(x_1\)，那么将最终结果设为 \(x_1\) 不会比设为 \(k\) 需要更多操作
同理，若 \(k \geq x_n\)，最终结果设为 \(x_n\) 不会比设为 \(k\) 更差

若 \(x_1 < k < x_n\), 那么我们假设 \(k\) 位于区间 \([x_i, x_{i + 1}]\) 之间, 即 \(x_i < k < x_{i + 1}\), 那么以 \(k\) 为分界可以将数组划分为两部分: \([x_1, \dots, x_i], [x_{i + 1}, \dots, x_n]\), 我们假设这两个区间的元素数量分别为 \(i, j\), 并且记 \(d_1 = k - x_i, \quad d_2 = x_{i + 1} - k\), 且以 \(k\) 为最终操作结果时操作次数为 \(n\), 那么，

以 \(x_i\) 为最终操作结果是操作次数为 \(n + (j \times d_2) - (i \times d_1)\), 即左区间的操作次数减少了，右区间的操作次数增加了
以 \(x_{i + 1}\) 为最终操作结果是操作次数为 \(n + (i \times d_1) - (j \times d_2)\), 即左区间的操作次数增加了，右区间的操作次数减少了

所以，若我们将最终操作结果由 \(k\) 变为距离 \(k\) 最近的一个元素时，结果会变为 \(n + \min \left((j \times d_2) - (i \times d_1), (i \times d_1) - (j \times d_2)\right)\), 显然, \(\min\) 中的两个值互为相反数，所以有 \(\min \left((j \times d_2) - (i \times d_1), (i \times d_1) - (j \times d_2)\right) \leq 0\), 即操作以后结果不会变差，推而广之，选数组中的元素作为最终结果不会比选非数组中的值作为结果更差，所以最后数组中的元素必定全部变为数组中某个元素值。

扫描线

从上面的证明中可以发现，数组中的元素在操作后肯定会变成元素中的某个值，那么怎么找出这个值呢？最简单的方法就是遍历，而根据数组范围，\(O(n^2)\) 方法肯定是行不通的，于是考虑到可以先对数组排序，再按序扫描，即可在 \(O(1)\) 时间计算操作次数。

具体来说，维护左区间和右区间的操作次数，随着遍历指针移动，左区间不断变大，操作次数也不断增加，右区间不断减小。而左区间的操作次数变化即新的结果与旧的结果的差乘以区间元素数量。

# Code language: Python
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        ans = 98765432100
        n = len(nums)
        left, right, pre = 0, sum(nums), 0
        for i, j in enumerate(nums):
            diff = j - pre
            left += diff * i
            right -= diff * (n - i)
            ans = min(ans, left + right)
            pre = j
        return ans

// Code language: Java
class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0x7fffffff, left = 0, right = 0, pre = 0;
        for (int cur: nums) right += cur;
        for (int i = 0, j = n; i < n; ++i, --j) {
            left += (nums[i] - pre) * i;
            right -= (nums[i] - pre) * j;
            ans = Math.min(ans, left + right);
            pre = nums[i];
        }
        return ans;
    }
}

// Code language: Cpp
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long ans = 0x7fffffff, left = 0, right = 0, pre = 0;
        for (int cur: nums) right += cur;
        for (int i = 0, j = n; i < n; ++i, --j) {
            left += (nums[i] - pre) * i;
            right -= (nums[i] - pre) * j;
            ans = min(ans, left + right);
            pre = nums[i];
        }
        return ans;
    }
};

时间复杂度: \(O(n \log n)\)
空间复杂度: \(O(\log n)\), 视排序算法而定