企业官网建设流程全解析

1. 题目复盘：3月15日这场机考的第二题到底考了什么

三月份那场蚂蚁春招开发岗的机考，我印象最深的反而不是压轴题，而是第二题。原因很简单：它看着人畜无害，一句"最少操作次数"就把不少人带进了沟里。有人上去就写贪心，有人想用平均值，还有人试图套动态规划，最后要么超时要么答案不对。其实这道题考的是排序加中位数的经典组合，思路一旦想清楚，代码量不超过十行。

1.1 题目还原与示例

根据考后多方回忆整理，题目大意如下：

给定一个长度为 n 的整数数组 nums，每次操作可以选择任意一个元素，将其增加 1 或者减少 1。请问最少需要多少次操作，才能让数组中所有元素的值变得相同？返回最少操作次数。

出题人没有包装任何业务场景，直接把核心问题摆出来。这种问法反而更考验基本功。我在蚂蚁相关的技术场景里见过类似需求的影子：多个数据源的值要拉齐到某个基准水位，总调整代价最小，本质上就是"把数组变成全等数组"的归一化问题。

看两个例子：

• 输入 nums = [1, 2, 3]，输出 2。把 1 加到 2 花 1 次，把 3 减到 2 花 1 次，合计 2 次。
• 输入 nums = [1, 10, 10]，输出 9。把 1 加到 10 花 9 次，另外两个不用动。

如果你刷过 LeetCode，会发现这就是第 462 题 Minimum Moves to Equal Array Elements II，原题几乎一模一样。刷过就是送分，没刷过就要在考场上现推，这也是这题最微妙的地方。

1.2 数据范围里藏着的两个信息

据回忆，约束条件是 1 <= n <= 10^5，0 <= nums[i] <= 10^9。这个范围一出来，基本就宣判了 O(n^2) 的暴力枚举和动态规划都不可行，能接受的最坏复杂度是 O(n log n)，最优是 O(n)。

更关键的是第二个信息：nums[i] 最大 10^9，n 最大 10^5，最极端情况下比如十万个数都是 10^9，其中一个数是 0，操作次数会到 9 * 10^13 这个量级。这在 32 位 int 里必然溢出。所以返回值类型、中间计算类型都得用 64 位整数。这是题里埋的第一个坑，后面讲实现时我会专门展开。

2. 解题思路推导：为什么答案锁定在中位数

2.1 先走一遍暴力思路，看看它告诉了我们什么

最朴素的想法是枚举最终目标值 x，然后计算所有元素到 x 的绝对差之和，取最小值。问题在于 x 的取值范围：nums[i] 最大 1e9，理论上 x 可以是 0 到 1e9 甚至超出这个范围的任何数，直接枚举不现实。

但暴力思路给了我们一个很重要的视角：这个问题的本质是找一个点 x，使所有数到它的绝对距离之和最小。定义函数：

f(x) = Σ |nums[i] - x|

这个函数是分段线性、凸的，画出来就是一条先下降、到达谷底后再上升的单谷曲线。单谷函数求最小值，理论上可以用三分搜索：每次取两个中点比较函数值，逐步缩小范围，复杂度 O(n log(值域))，也能过。但面试官如果听到你用三分，多半会追问一句"有没有更本质的做法"——这时候就该掏中位数了。

2.2 一个不需要高等数学的配对证明

为什么中位数是最优解，而不是平均值？可以用一个"配对消除"的方式直观证明。

先把数组排序成 a[0] <= a[1] <= ... <= a[n-1]，看最外面的一对 a[0] 和 a[n-1]。假设目标值 x 落在 [a[0], a[n-1]] 区间内，那么这两个数的贡献是：

(x - a[0]) + (a[n-1] - x) = a[n-1] - a[0]

这是一个常数，跟 x 具体取多少无关。但如果 x 落在区间外，比如 x < a[0]，贡献变成 (a[0] - x) + (a[n-1] - x) = a[n-1] + a[0] - 2x，比区间内的情况更大。这说明最优的 x 一定不会跑到当前最小值和最大值的外面去。

剥掉最外层这一对，剩下的事情变成在 a[1] 到 a[n-2] 上继续找"内部的中位数"。一层层剥下去，奇数长度时最后只剩下正中间那个数；偶数长度时剩下中间两个数之间的任意一个位置。这个位置就是中位数区间。

用这个配对论证来理解，比背结论牢靠得多。面试时如果能现场画出这个思路，面试官会认为你是真的理解，而不是背过题。

平均值为什么不行？看一个反例：[1, 2, 100]。平均值约 34.3，f(34.3) = 33.3 + 32.3 + 65.7，约为 131；中位数是 2，f(2) = 1 + 0 + 98 = 99，差了 32 次操作。原因是绝对值距离对离群点的惩罚是线性的，平均值会被 100 这个极端值拉偏，而中位数天然抵抗离群值。记住这个结论：绝对值距离对应中位数，平方距离才对应均值，两者不要混。

2.3 偶数长度时的细节处理

长度是偶数，比如 [1, 2, 3, 4]，中位数区间是 [2, 3]。取 x=2，代价为 1+0+1+2=4；取 x=3，代价为 2+1+0+1=4；取 x=2.5，代价为 1.5+0.5+0.5+1.5=4。三个值代价都一样。

所以实现上完全不用纠结取哪个中位数。最省事的写法是排序后取 nums[n/2]，也就是上中位数：奇数长度时它正好是正中间那个数，偶数长度时它是中间偏右的那个数。两种情况都正确。

到这里，整个算法就完整了，三步：

1. 排序，O(n log n)。
2. 取中位数 median = nums[n/2]。
3. 遍历累加 |nums[i] - median|，用 64 位整数。

总复杂度 O(n log n)，额外空间 O(1)（不计排序递归栈）。

3. 三种语言的实现与细节对比

3.1 Java 实现

import java.util.Arrays; public class MinOperations { public long minOperations(int[] nums) { Arrays.sort(nums); int n = nums.length; int median = nums[n / 2]; long ans = 0; for (int x : nums) { ans += Math.abs((long) x - median); } return ans; } public static void main(String[] args) { MinOperations solution = new MinOperations(); System.out.println(solution.minOperations(new int[]{1, 2, 3})); // 2 System.out.println(solution.minOperations(new int[]{1, 10, 10})); // 9 System.out.println(solution.minOperations(new int[]{1})); // 0 } }

Java 有几个注意点值得单独说。

Arrays.sort对 int[] 用的是双轴快速排序，平均 O(n log n)，但注意它是原地排序，会修改原数组。如果面试场景的原题不允许改动输入，需要先nums.clone()再排。笔试里一般不查这个，但当面试官问"如果输入不能被修改，你怎么处理"时，能说出这层考虑会加分。

Math.abs((long) x - median)这行非常关键。x 和 median 都是 int，如果不把第一个操作数强转成 long，两个 int 相减的结果还是 int，极端情况下会先溢出成负数，再取绝对值就得到完全错误的结果。先转 long 再减，再取绝对值，顺序不能乱。

返回值类型必须用 long。如果笔试函数签名写成了int minOperations(int[] nums)，大用例必然溢出，轻则丢测试点，重则整题白给。我见过不少人在这一下翻车。

3.2 C++ 实现

#include <vector> #include <algorithm> #include <cstdlib> class Solution { public: long long minOperations(std::vector<int> &nums) { std::sort(nums.begin(), nums.end()); int n = nums.size(); int median = nums[n / 2]; long long ans = 0; for (int x : nums) { ans += std::llabs(static_cast<long long>(x) - median); } return ans; } };

C++ 的坑和 Java 类似，但更隐蔽。绝对值函数有abs(int)、labs(long)、llabs(long long)几个版本，如果直接写std::abs(x - median)，x - median 是 int 运算，还是会在减法那一步溢出。所以必须先把 x 转成 long long 再参与减法。

写成static_cast<long long>(x) - median之后，右边的 median 是 int，会按类型提升规则自动转成 long long，这一步是安全的。反过来如果写x - median再转，溢出已经发生，神仙也救不回来。

std::sort本质是内省排序，最坏情况也是 O(n log n)，比快排退化到 O(n^2) 要稳。不过它要求随机访问迭代器，vector 没问题。另外std::sort同样会原地修改数组，和 Java 一样需要考虑输入是否可改动。

3.3 Python 实现

from typing import List class Solution: def min_operations(self, nums: List[int]) -> int: nums.sort() n = len(nums) median = nums[n // 2] return sum(abs(x - median) for x in nums)

Python 是最省心的：int 是任意精度，不存在溢出问题；nums.sort()原地排序，用的是 TimSort，对基本有序的数据还有额外优化。

有两个小地方值得注意。一是n // 2在 n=0 时会越界，但题目约束 n >= 1，笔试不用处理。如果本地写通用函数，可以加一行判空。二是生成器表达式sum(abs(x - median) for x in nums)在 10^5 数据量下毫无压力，但如果数据量到 10^7，可以改用map或手写循环，常数能小一些。笔试场景完全不需要纠结。

3.4 三份代码放一起，笔试语言怎么选

笔试时选你最有把握的语言，不要临时换。蚂蚁开发岗的笔试一般 Java、C++、Python 都接受。我的建议是：能用 5 分钟写完且保证不出 bug 的语言，就是最好的语言。这道题 Python 写起来最短，但如果平时主攻 Java，用 Java 写也完全稳，代码量差不了几行。

4. 在线自测：用例设计与结果验证

标题里带了"在线测试"，这里单独讲讲怎么自测。很多人笔试翻车不是思路错，而是边界没测出来就交了。

4.1 必备的边界用例集

这里说下"最大规模"怎么验证。最靠谱的办法是写一个暴力解法，生成 n 比较小的随机数组做对拍。暴力解可以枚举目标值 x，因为最优解一定落在数组最小值和最大值之间，枚举这个区间里的每个整数即可。Python 写很快：

def brute(nums): lo, hi = min(nums), max(nums) best = float('inf') for target in range(lo, hi + 1): cost = sum(abs(x - target) for x in nums) best = min(best, cost) return best

然后随机生成 1000 组 n <= 8、数值在 [-20, 20] 的数组，把优化解和暴力解逐一对照。全部一致，基本就能放心。暴力枚举只在数值区间小时可用，正式提交别拿它跑大数据。

4.2 复杂度的实际表现

n=10^5 时，排序加一次线性扫描，Java 和 C++ 都在十几毫秒内完成，Python 也在几十毫秒内。在线笔试平台一般单题限时 1 到 2 秒，O(n log n) 完全没有压力。真正要避免的是在 Python 里用嵌套列表推导，比如sum([abs(x - median) for x in nums])，这会多建一个列表，白白多一遍扫描。用生成器表达式就好。

空间复杂度三个版本都是 O(1) 的额外空间，不会触发内存限制。

4.3 考场上完整的自测流程

机考一般允许本地编译运行，也允许提交看部分测试点。我的固定流程是：

1. 先写一个能跑通的最小版本，把题目给的样例跑对。
2. 用上面那张边界表逐条过一遍，重点关注 n=1 和偶数长度。
3. 随机生成小规模数组，和暴力解对拍，跑几百组。
4. 检查返回值类型和 abs 溢出位置。
5. 最后提交。

这五步做完，这个题基本就是满分了。我见过太多人前两个样例跑了通过就急着交，结果挂在一个大数溢出或者偶数长度的隐藏用例上，非常可惜。多花两分钟自测，比考完后悔要划算得多。

5. 面试官可能追问的四个变体与应对思路

大厂笔试只是敲门砖，这道题真正拉开差距的环节是后面的面试追问。面试官很可能拿着你的代码，问"这个题还能怎么变"。下面四个变体是概率最高的，建议提前过一遍。

5.1 变体一：每次把 n-1 个元素同时加 1

这是 LeetCode 453 的经典题。给定数组，每次操作可以选择 n-1 个元素同时加 1，求让所有元素相等的最少次数。

这个题思路完全不一样，不能再套中位数。核心观察是：反过来看，相当于每次让一个元素相对减少 1。最终每个元素被操作的次数是 X - nums[i]，其中 X 是最终相等值。总操作数满足 n * (X - min(nums)) = sum(nums) - n * min(nums)，于是答案是：

def min_moves_453(nums): return sum(nums) - len(nums) * min(nums)

也就是只要求出数组总和与最小值的差，一次遍历就搞定，连排序都不用。注意答案仍然可能非常大，求和用 64 位。

5.2 变体二：每个元素带权重

如果第 i 个元素调整 1 个单位要花 w[i] 的代价，问总调整代价最小是多少。这时代价函数变成 f(x) = Σ w[i] * |x - a[i]|，最优解升级为带权中位数。

做法是：按值排序，按权重累加，找到第一个使累计权重不小于总权重一半的位置，这个位置的值就是目标值。

def weighted_median(vals, weights): pairs = sorted(zip(vals, weights)) total = sum(weights) acc = 0 for val, w in pairs: acc += w if acc * 2 >= total: return val

直观理解：把每个元素想成数轴上的点，权重是点的质量。带权距离最小的位置不是物理重心（加权平均），而是带权中位数。面试时能把这个类比讲出来，比背公式有说服力得多。

5.3 变体三：二维平面上的推广

给 n 个平面点，每次操作可以把一个点的 x 坐标或 y 坐标加减 1，求让所有点重合的最少操作次数。

因为 x 方向的调整和 y 方向的调整互不影响，总代价等于 x 方向代价加 y 方向代价。所以把 x 坐标单独提出来排序求中位数，y 坐标也单独求中位数，两个维度的代价相加即可。这是曼哈顿距离的经典性质：高维问题可以按维度分解。如果面试官把曼哈顿距离换成欧几里得距离，那才是真正复杂的几何问题，需要别的方法，但那就超出这道题的范畴了。

5.4 变体四：不排序能不能更快

排序是 O(n log n)，但找中位数本身可以做到 O(n) 平均时间。方法是快速选择（quickselect），也就是快速排序的减治版本：每次 partition 后只递归含有第 k 小元素的那一侧，平均 O(n)，最坏 O(n^2)，随机化主元可以规避最坏情况。

C++ 里直接用现成的std::nth_element：

std::nth_element(nums.begin(), nums.begin() + n / 2, nums.end()); int median = nums[n / 2];

这行执行完后，nums[n/2] 就是按序排列时该在位置的元素，左边都不大于它，右边都不小于它。Java 没有现成的 API，可以手写 quickselect，但 10^5 数据量下排序的常数已经足够小，没必要增加出错风险。

面试时主动说一句"这道题其实可以用 quickselect 优化到平均 O(n)，但排序在这个数据范围已经足够"，会让面试官觉得你对复杂度边界有清晰感知，这是实打实的加分项。

6. 复盘：这道题最容易丢分的五个位置

最后聊聊我观察到的常见失分点，以及考场上的节奏建议。

6.1 五个高频错误

第一，用了平均值。这是最大的坑。平均值只对平方误差最优，对绝对误差不优。一定要在脑子里建立"绝对值距离对应中位数、平方距离对应均值"的映射，这个考点面试出现频率极高。

第二，返回值类型写 int。题目数据范围明摆着会溢出，写 int 就是在送测试点。笔试前可以养成习惯：只要涉及求和、累加、差值，且数值范围超过 10^9，一律用 long 或 long long。

第三，abs 操作的溢出顺序。Java 里Math.abs(x - median)没强转，C++ 里 abs 前没转 long long，这是最隐蔽的 bug，本地小数据测不出来，大数据直接错。正确顺序是：先转 64 位，再相减，再取绝对值。

第四，偶数长度数组的纠结。有人论证到一半开始想"是不是要取平均值"，把自己绕晕了。记住结论：偶数长度取 n/2 和 (n-1)/2 结果相同，取哪个都行，不用犹豫。

第五，不做边界测试直接提交。至少跑一遍 n=1、全相等、负数混合、偶数长度这四个用例，能拦下绝大多数低级错误。我在模拟面试里见过有人样例过了就交，结果 n=1 时中位数下标直接越界，太冤了。

6.2 考场上的节奏建议

机考第二题通常是"会者不难"，它在整套卷里的定位就是考察你能否在 15 分钟内完成从读题、推导、编码到自测的完整闭环。我自己在考场上花了四分钟在草稿纸上推了推中位数的配对论证，确认偶数情况没问题，然后才开始写代码，一气呵成没有返工。写完后用边界用例过了一遍，检查了 long 类型，才提交。

这道题真正的价值不在它本身，而在背后的推广链：从一维中位数到带权中位数，再到多维分解和快速选择。把这串东西吃透，蚂蚁这场笔试想考察的"数学直觉加基础算法功底加编码稳健性"三个维度，你就都覆盖到了。考前如果能顺手把 LeetCode 462 和 453 两道题都过一遍，这道题就是纯粹的送分题。