Medium

题目描述

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

在一次移动中，你可以使数组中的一个元素加 1 或者减 1。

测试用例保证答案在 32 位整数范围内。

示例 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

解题思路

这是一个经典的数学优化问题。我们需要找到一个目标值，使得所有元素到这个目标值的距离之和最小。

核心思路： 要使所有元素相等，最优的目标值是数组的中位数。这是因为中位数具有使所有元素到它的绝对偏差之和最小的性质。

数学证明：

  • 对于任意目标值 x，总移动次数为 Σ|nums[i] - x|
  • 当 x 为中位数时，这个和达到最小值
  • 这是因为中位数将数组分为两部分，左边元素个数 ≤ 右边元素个数（或相等）

算法步骤：

  1. 对数组进行排序
  2. 找到中位数（对于偶数个元素，选择中间两个元素中的任意一个都可以）
  3. 计算所有元素到中位数的距离之和

时间复杂度分析：

  • 排序：O(n log n)
  • 计算距离和：O(n)
  • 总体：O(n log n)

代码实现

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int median = nums[nums.size() / 2];
        int moves = 0;
        for (int num : nums) {
            moves += abs(num - median);
        }
        return moves;
    }
};

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        median = nums[len(nums) // 2]
        return sum(abs(num - median) for num in nums)

public class Solution {
    public int MinMoves2(int[] nums) {
        Array.Sort(nums);
        int median = nums[nums.Length / 2];
        int moves = 0;
        foreach (int num in nums) {
            moves += Math.Abs(num - median);
        }
        return moves;
    }
}

var minMoves2 = function(nums) {
    nums.sort((a, b) => a - b);
    const median = nums[Math.floor(nums.length / 2)];
    return nums.reduce((moves, num) => moves + Math.abs(num - median), 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要是排序操作的时间复杂度
空间复杂度O(1)只使用了常数额外空间（排序为原地排序）

相关题目