Why is the median used instead of the mean in this problem?

Using the median minimizes the sum of absolute differences, which directly reduces the total number of moves required.

Can the solution handle negative numbers in the array?

Yes, the median approach works for both positive and negative integers since it calculates absolute differences.

What is the time complexity of this solution?

Sorting dominates the time complexity at O(n log n), while summing absolute differences is O(n).

Does the array length affect the choice of median?

For even-length arrays, any element between the two middle elements can serve as the median without changing the minimal move total.

How does GhostInterview help with Minimum Moves to Equal Array Elements II?

It provides direct guidance on sorting, median selection, and calculating absolute differences to find the minimal move count efficiently.

#462

Medium

auto_awesome数组·数学

LeetCode 题解工作台

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

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。测试用例经过设计以使答案在 32 位整数范围内。示例 1：输入： nums = [1,2,3] 输出： 2 解释：只需要两次操作（每次操作指南使…

数组数学排序

题目描述

给你一个长度为 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⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 中位数

这个问题可以抽象为，在数轴上有 $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)$ 。

相似题目：

1

2

3

4

5

6

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)

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to sorting, and space complexity is O(1) if sorting is in-place. Computing differences afterward is linear in n.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Mentions array length up to 105 and presence of negative numbers.
question_mark
Hints at using a central value to minimize total moves.
question_mark
Tests understanding of absolute differences and sorting.

warning

常见陷阱

外企场景

error
Targeting mean instead of median, which can increase move count.
error
Ignoring negative numbers when calculating differences.
error
Failing to sort first, making median selection ambiguous.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum moves if only increment operations are allowed.
arrow_right_alt
Find minimum moves when array elements must reach a value divisible by k.
arrow_right_alt
Determine minimum moves to equal elements when allowed moves are +/- d instead of 1.

help

常见问题

外企场景

继续练习

#539 最小时间差 #368 最大整除子集 #628 三个数的最大乘积