先交代一下背景2026年春招笔试里算法岗这套卷子的第一题叫“全相等”题目本身不难但它出现在卷首承担的任务很特殊——把心态稳住、把基础盘接住。我陪人复盘时发现不少同学在五分钟内能写出能过的代码可被追问“为什么中位数是最优解”时反而卡住。这题真正值得写的不是代码本身而是背后的推导链路和那些容易被忽略的边界细节。这篇文章把题面、推导、三种语言实现、在线验证方法和几个高频变形一起讲透给准备笔试的同学做一份可直接复用的笔记。1. 这道“全相等”在春招笔试中的定位与考察意图1.1 第一题通常承担的角色算法岗笔试普遍是2到4道题时间两小时上下。第一题大概率是“签到题”但也因为这样很多人反而栽跟头——要么读题太快漏掉操作限制要么觉得简单就不写测试用例直接提交后才发现溢出或边界错误。全相等这题在套路结构上非常标准数组、操作、最小代价三个要素齐全但没有任何复杂数据结构排序加一行统计就能解决。它本质上是考察“能不能识别出绝对值和最小化的本质”。我自己的经验是不要把签到题当“送分题”对待要当“热身题”和“心态题”。写题速度固然重要但第一题如果栽了后面的状态会受很大影响。这套卷把全相等放第一题明显就是想让多数人先拿稳一血把节奏带起来。1.2 考官到底想看什么一道全相等对应了三个能力点。第一是建模能力能否把“操作次数最少”抽象成“选一个目标值让所有数到它的绝对距离总和最小”第二是算法设计能力能否从枚举优化到排序后取中位数并能给出复杂度分析第三是基础功三种语言里能不能写出无溢出、边界正确的代码特别是当数组元素范围拉到很大时。这些能力都不是靠背题能练出来的。我见过不少人的准备方式是刷题量堆上去但问到“为什么绝对值距离和的最优解是中位数而不是平均数”时只能说“这题都是这么做的”。这种回答在笔试环节没事到了面试撕题环节基本会被立刻追问到底。把原理吃透才是这题真正的价值所在。2. 整理后的题面、数据范围与三组自测样例2.1 题面与输入输出约定题目回忆版整理如下给定一个长度为 n 的整数数组 a每次操作可以选中一个下标 i让 a[i] 加 1 或减 1。求最少需要多少次操作才能让数组中所有元素的值相等。输入格式 第一行一个整数 n表示数组长度。第二行 n 个整数表示数组元素。输出格式 一行一个整数表示最小操作次数。数据范围 n 最大到 10^5a[i] 可以为负数绝对值不超过 10^9。看到这个数据范围第一反应就是答案可能超过 int 范围。n 是 10^5每个数幅度 10^9最坏情况答案量级在 10^14 左右long/long long 起步。Java 用 longC 用 long longPython 不需要考虑整数天然够用。2.2 三组测试样例我在考场复盘时习惯构造几组“带心机”的样例而不是只用题目给的示例跑一遍。这三组是验证时最常用的输入期望输出说明5 / 1 2 3 4 56奇数长度目标取中位数 34 / 1 1 100 100198偶数长度目标可取区间内任意值1 / 420单元素边界情况第一组是最经典的示例目标取 3代价为 210126。第二组有意思得多数组按序排好后是 1、1、100、100中位数区间是 [1, 100]目标不管取 1、100 还是 50代价都是 198。这正好引出一个容易被忽略的结论偶数长度时目标只要落在中间两个数之间代价相同。第三组是边界情况n1 时答案必然是 0排序后 target 取唯一元素即可。2.3 样例里的“小心机”第二组样例是区分“背模板”和“理解原理”的好工具。如果只记住“排序后取 a[n/2]”输出 198这没错但如果被问“取 a[n/2-1] 行不行”也能输出 198这就说明你真正懂了。实际写代码时偶数组取 a[n/2] 或 a[n/2-1] 都正确代价相同。没有哪个更好只是习惯问题。C 里 sort 后下标从 0 开始n/2 是上中位数Java 和 Python 同理。这个细节在笔试里不会造成错误但在面试中能体现边界考虑是否周全。这类小心机在真实题目里不少见尤其第一题出题人会故意放一个不疼不痒的迷惑点看你能不能识别出来。全相等的迷惑点就是平均数很多人下意识觉得“让所有数相等那不就是变成平均值吗”而正确答案偏偏是中位数。这个反直觉点下一节详细展开。3. 从暴力枚举到排序中位数的三步推导3.1 暴力枚举的复杂度瓶颈最直接的思路枚举所有可能的目标值 x对每个 x 计算 sum(|a[i]-x|)取最小值。这个思路完全正确但复杂度是 O(n × range)其中 range 是 a[i] 的范围。数据范围里 a[i] 绝对值到 10^9range 接近 2×10^9n 是 10^5运算量达到 2×10^14 量级。这个规模在笔试环境下显然跑不完。不过暴力枚举在“对拍验证”阶段非常有用我后面会专门讲怎么用暴力程序和小数据量随机数组互相验证确保高效写法没有写错。笔试里这种思路的价值不在于拿满分而在于作为参照物。3.2 凸函数视角三分搜值可行但不优雅稍微观察一下 f(x) sum(|a[i]-x|)绝对值函数是凸函数非负加权求和仍然是凸函数。凸函数在区间上一定存在唯一的最小值点或者一段平坦区间所以可以用三分搜索在 [min(a), max(a)] 范围内找最优目标值。三分法的复杂度是 O(n log range)也就是 10^5 × 31 次左右的绝对值计算完全能过。但这个方法有个问题实现起来比排序取中位数复杂精度和边界处理也容易出 bug。整数三分需要仔细处理区间收缩条件稍不注意就会死循环或漏掉端点。笔试第一题的原则是“用最稳的方法拿最快的分”三分法虽然正确但不够优雅。3.3 排序后的配对思考真正的关键一步是把数组排序然后成对观察。排序后 a[0] 最小a[n-1] 最大。考虑这两个点到目标 x 的绝对距离之和当 x 落在 [a[0], a[n-1]] 区间内时|a[0]-x| |a[n-1]-x| 恒等于 a[n-1]-a[0]也就是区间长度。当 x 落在这个区间外时这个和会变大。这给了我们一个“剥洋葱”的思路最优目标一定在最值区间内部否则第一项会白损失。剥掉最外层一对后剩下的数组 [a[1], a[n-2]] 又变成了同样的子问题。不断向内剥直到剩一个点或两个点。n 为奇数最后剩下中间那个点它就是排序后的中位数也是最优目标值。n 为偶数最后剩下中间两个点最优目标可以是它们之间的任意值代价相同。这个配对思路的价值在于它不需要任何高等数学工具画一条数轴就能跟面试官讲清楚。从暴力到三分的进步是算法层面的优化从三分到排序取中位数的进步则是模型识别层面的优化——识别出了这个问题的本质结构。这也是为什么这题被放在第一题它考察的正是从“能算”到“会算”的思维跳跃能力。4. 中位数最优性的严格证明与常见误区4.1 配对夹逼的完整证明为了让结论更有说服力我把上面的配对思路写成更严格的形式。假设排序后的数组为 b[0] ≤ b[1] ≤ ... ≤ b[n-1]目标为 x。先把整个数组的和式写成配对形式sum(|b[i]-x|) (|b[0]-x| |b[n-1]-x|) (|b[1]-x| |b[n-2]-x|) ...对任意一对 (b[i], b[j])其中 ij有不等式|x-b[i]| |x-b[j]| ≥ b[j] - b[i]当且仅当 x 位于 [b[i], b[j]] 时取等号。于是总代价有下界sum(|b[i]-x|) ≥ (b[n-1]-b[0]) (b[n-2]-b[1]) ...如果 x 能同时落在每一对的内侧下界就能达到。这个“同时落在每一对内侧”的条件最终要求 x 落在最内层的区间内n 为奇数时最内层是一个点 b[n/2]x 必须等于它这就是中位数。n 为偶数时最内层是区间 [b[n/2-1], b[n/2]]x 取区间内任意值都能达到下界。所以中位数的正确性不是一个经验结论而是严格推导出来的。这段证明在面试中讲出来会明显区别于“背答案”的候选人。4.2 均值不是最优一个反例平均数误区是这个题最经典的陷阱。很多人觉得“全相等当然是把所有数变成平均值”但平均值只有在误差平方和最小化时才是最优。这题用的是绝对值距离绝对值对应的最优中心是中位数。举一个直接反例数组 [1, 2, 100]。平均值约 34.33中位数是 2。如果目标是 2代价是 |1-2| |2-2| |100-2| 1 0 98 99。如果目标是 34代价是 33 32 66 131目标是 33代价是 32 31 67 130。不管怎么取均值附近的整数代价都远大于取中位数的代价。深层原因是均值对极端值极其敏感而绝对值距离函数的增长是线性的中位数对离群点有很强的鲁棒性。换到实际场景理解一次极端操作的成本与距离成正比而不是与距离的平方成正比所以不做任何“惩罚放大”首选目标自然跟着中间位置走而不是被极端值拽走。这个反例也建议笔试前多拿几组随机数据验证巩固直觉。5. Java/C/Python三版实现与边界细节5.1 Java实现import java.util.Arrays; import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long[] a new long[n]; for (int i 0; i n; i) { a[i] sc.nextLong(); } Arrays.sort(a); long target a[n / 2]; long ans 0; for (long x : a) { ans Math.abs(x - target); } System.out.println(ans); } }Java 里最值得注意的就是数据类型。a[i] 范围到 10^9用 int 存没问题但累加距离时 ans 的最大值是 n × range也就是 10^5 × 2×10^9 2×10^14远超 int。直接把数组声明成 long[]既避开了求和溢出也省了后续类型转换的麻烦。读取方面笔试环境一般给标准输入用 Scanner 足够。如果追求更快的输入可以用 BufferedReader 手写解析但对于 10^5 规模的数据Scanner 完全够用没必要增加复杂度。5.2 C实现#include bits/stdc.h using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr);int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long target a[n / 2]; long long ans 0; for (long long x : a) { ans llabs(x - target); } cout ans \n; return 0;}C 版要提两个细节。第一个是 ios::sync_with_stdio(false) 和 cin.tie(nullptr)这几乎是竞赛代码的标配能显著加快标准输入输出。第二个是绝对值函数如果 x 和 target 都是 long longabs 在某些编译环境下返回的是 int会被截断造成错误稳妥起见直接用 llabs。有些人会写ans abs(x - target)在数据范围小的时候没问题但遇到 10^9 级别的差值就不安全了。统一用 llabs或者干脆每次都转成 long long 再算能避免所有隐患。还有一个边界点是 n 为 1 时vector 里只有一个元素a[n/2] 就是 a[0]循环求和为 0正确输出不需要额外特判。5.3 Python实现import sysdef main(): data sys.stdin.read().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) a.sort() target a[n // 2] ans sum(abs(x - target) for x in a) print(ans)ifname main: main()Python 版最需要注意输入解析。笔试中行尾可能有多余空格甚至整个输入横跨多行用 sys.stdin.read().split() 统一分割后转 int是最稳妥的读取方式。如果只用 input().split()遇到空白行或数据折行时会比较被动。target a[n // 2]对奇数长度取正中对偶数长度取上中位数代价正确。Python 的整数没有溢出概念sum 累加多少位都能存下这也是 Python 写算法题的一个省心点。性能上10^5 规模的排序和求和都在毫秒级没有任何压力。5.4 复杂度与常见坑三份代码的时间复杂度完全一致排序 O(n log n)求和 O(n)总复杂度 O(n log n)空间复杂度 O(1)不考虑输入数组本身的存储。这个复杂度在 10^5 的数据量下非常安全。常见坑集中在这几个地方坑点后果规避方式答案用 int 累加溢出变成负数用 long/long longC 用 abs 处理 long long可能截断用 llabs偶数长度取中位数疑惑心态波动理解区间等价性Python 读取只用 input().split()多行数据出错用 sys.stdin.read().split()我个人推荐的做法无论题目数据范围多“温柔”一律按最坏情况设计数据类型宁可多写两个字节不赌数据弱。这是刷题踩坑换来的经验笔试环境里没有调试机会稳健是第一优先级。6. 在线自测、随机对拍与三道高频变形题6.1 在线评测与自测方法笔试系统一般按“输入示例-输出示例”的格式做全量数据评测本地自测时最好手敲几组样例确认输出。除了前面表格里的三组基础样例再推荐几组专项自测负数混合4 / -5 -1 0 3排序后取中位数 -1代价 40149。全部相等的数组5 / 7 7 7 7 7代价 0。极端跨度2 / -1000000000 1000000000代价 2000000000正好验证 long 类型。每组样例跑完都对一下预期结果。这里多说一句笔试环境里如果系统报错不如预期优先检查输入解析而不是算法逻辑。很多“答案错误”其实是多读了空行、数组长度没对齐之类的小问题。6.2 随机数据对拍脚本比手敲样例更可靠的方式是对拍。写一个暴力枚举版本再写一个排序取中位数版本生成随机小数组对比两个版本的结果。代码不复杂但能一次性覆盖成千上万组边界情况比自己想测试用例全面得多。import randomdef brute(a): lo, hi min(a), max(a) best float(inf) for x in range(lo, hi 1): cost sum(abs(v - x) for v in a) best min(best, cost) return bestdef solve(a): b sorted(a) target b[len(b) // 2] return sum(abs(v - target) for v in b)for _ in range(10000): n random.randint(1, 8) a [random.randint(-5, 10) for _ in range(n)] if brute(a) ! solve(a): print(mismatch:, a, brute(a), solve(a)) break else: print(all ok)这里的关键是让暴力枚举的 range 不要太大所以随机数范围控制在 -5 到 10 之间。对拍一万组理论上能覆盖绝大多数边界形态包括奇偶长度、负数、全等数组。笔试前花五分钟写个对拍脚本比盯着代码反复读更有效。6.3 三道高频变形题全相等的变形在面试里出现频率很高核心都是绝对值距离最小化的变体。第一道变形只能对元素加 1不能减 1求最少操作次数。既然不能减目标值只能取数组最大值答案就是 sum(max(a)-a[i])。负数同样适用目标值依旧是最大值。第二道变形每次操作可以把相邻两个元素一个加 1、另一个减 1求使所有元素相等的最少操作次数。这个版本的核心是前缀和先判断总和能否被 n 整除不能则无解能则计算每个元素与平均值的差值累加前缀和的绝对值就是最少操作次数。原理在于每次相邻操作相当于移动一个单位的“差额”从左到右逐个抹平。第三道变形带权重的全相等每个元素有权重 w[i]求最小化 sum(w[i]·|a[i]-x|)。解法是把权重看成该位置有 w[i] 个重复点找加权中位数也就是前缀权重首次超过总权重一半的位置。这个变形在工程场景里更接近“选址问题”——在数轴上选一个仓库位置使所有客户的加权配送距离最小。变形题的意义在于中位数这一个结论能串起多个看似不同的题目。刷题时如果每道独立背代码很快就会忘理解了“绝对值距离最小化”这个模型变一个条件就能现场推一个解法出来这才是春招真正想看到的能力。最后再分享一个个人习惯每次写完这类“排序取中位数”的题我都会顺手在代码里保留一次暴力对拍的注释标注出关键样例和复杂度结论。笔试是限时游戏但准备阶段不是——把每道题的“为什么”拆透彻考场上才能毫不犹豫地写。全相等这道题不复杂但它值得认真对待因为它背后代表的建模能力恰恰是大厂算法岗最看重的底层素质。