小鲸鱼的梦境
0%

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

发表于 分类于 Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目

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 ≤ 105
  • −109 ≤ nums[i] ≤ 109

相似题目

题解

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

证明

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

设数组元素已经排序（非递减），记为 [x1, x2, …, xn], 假设最终数组元素中全部变为 k, 且对 ∀i, xi ≠ k

  • 若 k ≤ x1， 即 k 小于数组中最小的值 x1，那么将最终结果设为 x1 不会比设为 k 需要更多操作
  • 同理，若 k ≥ xn，最终结果设为 xn 不会比设为 k 更差

若 x1 < k < xn, 那么我们假设 k 位于区间 [xi, xi + 1] 之间, 即 xi < k < xi + 1, 那么以 k 为分界可以将数组划分为两部分: [x1, …, xi], [xi + 1, …, xn], 我们假设这两个区间的元素数量分别为 i, j, 并且记 d1 = k − xi,  d2 = xi + 1 − k, 且以 k 为最终操作结果时操作次数为 n, 那么，

  • 以 xi 为最终操作结果是操作次数为 n + (j × d2) − (i × d1), 即左区间的操作次数减少了，右区间的操作次数增加了
  • 以 xi + 1 为最终操作结果是操作次数为 n + (i × d1) − (j × d2), 即左区间的操作次数增加了，右区间的操作次数减少了

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

扫描线

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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(nlog n)
  • 空间复杂度: O(log n), 视排序算法而定
--- ♥ end ♥ ---

欢迎关注我呀~