Question

462. 最小操作次数使数组元素相等 II

English Version

题目描述

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

解法

方法一：排序 + 中位数

这个问题可以抽象为，在数轴上有 $n$ 个点，找到一个点使得所有点到该点的距离之和最小。答案为 $n$ 个点的中位数。

中位数有这样的性质：所有数与中位数的距离之和最小。

证明：

首先，给定一个从小到大的数列 $a_1, a_2, \cdots, a_n$，我们假设 $x$ 是从 $a_1$ 到 $a_n$ 与其距离之和最小的点，显然 $x$ 必须位于 $a_1$ 和 $a_n$ 之间。而由于 $a_1$ 与 $a_n$ 与 $x$ 的距离之和都相等，都等于 $a_n-a_1$，因此，接下来不考虑 $a_1$ 和 $a_n$，我们只考虑 $a_2, a_3, \cdots, a_{n-1}$，这样的话，我们就可以把问题转化为在 $a_2, a_3, \cdots, a_{n-1}$ 中找到一个点与其距离之和最小，依此类推，我们最后可以得出结论：在一个数列中，中位数与其余数的距离之和最小。

在这个问题中，我们可以先对数组进行排序，然后找到中位数，最后计算所有数与中位数的距离之和即可。

时间复杂度 $O(n\log n)$，空间复杂度 $O(\log n)$。

相似题目：

• 296. 最佳的碰头地点
• 2448. 使数组相等的最小开销

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    nums.sort()
    k = nums[len(nums) >> 1]
    return sum(abs(v - k) for v in nums)

class Solution {
  public int minMoves2(int[] nums) {
    Arrays.sort(nums);
    int k = nums[nums.length >> 1];
    int ans = 0;
    for (int v : nums) {
      ans += Math.abs(v - k);
    }
    return ans;
  }
}

class Solution {
public:
  int minMoves2(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int k = nums[nums.size() >> 1];
    int ans = 0;
    for (int& v : nums) ans += abs(v - k);
    return ans;
  }
};

func minMoves2(nums []int) int {
  sort.Ints(nums)
  k := nums[len(nums)>>1]
  ans := 0
  for _, v := range nums {
    ans += abs(v - k)
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function minMoves2(nums: number[]): number {
  nums.sort((a, b) => a - b);
  const mid = nums[nums.length >> 1];
  return nums.reduce((r, v) => r + Math.abs(v - mid), 0);
}

impl Solution {
  pub fn min_moves2(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let mid = nums[nums.len() / 2];
    let mut res = 0;
    for num in nums.iter() {
      res += (num - mid).abs();
    }
    res
  }
}

方法二：排序 + 前缀和

如果我们不知道中位数的性质，也可以使用前缀和的方法来求解。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    def move(i):
      v = nums[i]
      a = v * i - s[i]
      b = s[-1] - s[i + 1] - v * (n - i - 1)
      return a + b

    nums.sort()
    s = [0] + list(accumulate(nums))
    n = len(nums)
    return min(move(i) for i in range(n))