这次阿里巴巴春招3月28日开发岗的笔试第二题“不稳定or相似”在不少技术群里讨论热度一直没降。题面本身不长核心就一句话给你一个数组和一个阈值k问能不能重排这个数组使得排序后相邻两个数的绝对差都不超过k。但就是这句话让不少同学第一题顺利AC之后卡在这个看似简单的第二题上。我把这道题的完整复盘、解题思路、Java/C/Python三种实现以及复习和测试过程中遇到的坑一起整理出来给接下来要参加各厂春招的同学做个参考。1. 题目复盘先搞清楚“不稳定”和“相似”到底在问什么1.1 社区流传的题目版本笔试结束后我综合了牛客、脉脉、几个技术讨论群里考生的回忆题目描述大致是这样的给定一个长度为n的整数数组a和一个非负整数k。判断是否存在一种“不稳定排序”后的排列b使得b中任意相邻元素的绝对差都不超过k。如果存在输出满足条件的排列如果不存在输出-1。不同考生回忆的细节略有出入有的说“数组元素范围在int内”有的说“n最大是10^5”但核心判定逻辑没有歧义。这道题放在开发岗第二题的位置结合“不稳定排序”这个词确实很容易让人第一眼就往快速排序、堆排序、选择排序这些算法上想。我一开始也以为要手写某个不稳定排序实际上完全不是。1.2 “不稳定”是一个精心设计的误导项排序算法的稳定性指的是当排序的关键字相等时稳定排序能保持元素原本的相对顺序不稳定排序则不保证这一点。冒泡排序、插入排序、归并排序是稳定的快速排序、选择排序、堆排序是不稳定的。题目里出现“不稳定”这个词很多人会下意识理解成“我可以任意打乱数组只要能构造出一种排列满足条件”。这个理解是错的而且错得很关键。无论排序算法稳定还是不稳定对一个数组做升序排序后输出的数值序列本身是唯一的。稳定不稳定影响的只是相等元素之间的内部顺序而那些相等元素的值是相同的所以在结果序列里它们无论谁在前谁在后从数值上看完全一样。比如 [3, 1, 2] 升序排序稳定和不稳定排序输出的都是 [1, 2, 3][2, 1, 2] 排序后两个2交换位置输出仍然是 [2, 2, 1]数值序列没有区别。放到这道题里我们要判断的是“是否存在一种排列使相邻差都不超过k”。既然所有排序算法得到的数值序列本质上相同那么这个问题就退化成对原数组做一次排序然后检查排序后数组的相邻差最大值是否不超过k。不需要真的去分析用哪种不稳定排序也不需要自己实现排序。1.3 “相似”的判定标准题面里的“相似”定义是“排序后相邻元素差的绝对值不超过k”。这是一个非常宽松的相似度定义只关心相邻元素之间的跨度不关心整体趋势、不关心均值、不关心元素分布。把问题翻译成数学语言就是存在排列 b1, b2, ..., bn使得对所有 i ∈ [1, n-1]都有 |bi - b(i1)| ≤ k。这里的关键点在于如果我们能做到那个满足条件的排列就是升序排列因为升序排列会把任意两个元素之间的跨度压缩到最小。如果升序排列都无法满足相邻差约束那任何其他排列更不可能满足。这个直觉可以用一个很简单的逻辑证明n个点排列在数轴上相邻点之间要有n-1条边而首尾两点的距离 max(a) - min(a) 是固定的它必须被这n-1条边的长度覆盖。如果每条边长度最多是k那么总跨度最多是 k*(n-1)。升序排列已经让每条边对应数轴上相邻的两个元素跨度最小任何非升序排列都会让某些边跨越更多元素使得跨度更大。所以结论非常干净先排序再逐对检查差值只要有一个差值超过k就输出-1否则输出排序后的数组。这个结论既出人意料又在情理之中出题人用“不稳定”三个字把不少人带偏了。2. 考场上的思考链路从暴力解法到关键结论2.1 先确认暴力解法能不能用假设我在考场上没有一眼看出上面的结论最稳妥的第一步是先写一个暴力搜索确认题目的规模允许什么复杂度的算法。如果n很小比如n ≤ 8可以直接枚举所有排列逐个检查相邻差。全排列数量是n!n8时有40320种n10时有3628800种勉强能跑n12就直接爆炸了。所以暴力枚举只适合用来验证小数据不能作为正解。还有一种“伪暴力”思路从小到大依次放数每次选择一个当前还没用过的数要求它和上一个放的数的差不超过k然后继续DFS。这个搜索在最坏情况下是指数级的但加上排序和贪心剪枝后对小数据是OK的。然而真实笔试的n通常会到10^5甚至更大DFS基本不可能通过。所以看到“数组重排相邻差”这种组合时第一反应应该是这道题大概率不是搜索题而是排序题或者贪心题。从暴力解法能确认一件事如果存在满足条件的排列那么一定有一个单调的排列升序或降序也满足条件。因为我们可以把任意两个相邻差超过k的元素对拆开通过调整顺序让更接近的数靠在一起。这个直觉在验证小数据时会有帮助。2.2 关键结论为什么只需要看升序排列要严格证明“升序排列是所有排列中相邻差最不容易超过k的”可以用反证法。假设存在一个满足条件的排列P且P不是升序。那么在P中一定存在某个逆序对即某个位置i满足 P[i] P[i1]。如果我们交换这两个相邻逆序元素考虑交换前后相邻差的变化交换只影响两对相邻关系P[i-1]和P[i]、P[i]和P[i1]以及交换后的P[i-1]和P[i1]、P[i1]和P[i]其他位置不受影响。交换相邻逆序对之后序列会变得更有序相邻元素之间的跨度不会增大。反复执行这样的交换最终得到升序排列而任何一次交换都不会让原本满足相邻差约束的序列变得不满足。因此只要有一个满足条件的排列存在升序排列就一定也满足条件。这个结论用大白话说就是要让相邻元素尽可能接近最合理的排列就是把所有数从小到大排好。任何打乱顺序的做法只会让某些本应相邻的差不大的数被拉开让本应离得远的数凑到一起。2.3 一个非常有用的前置剪枝在真正写排序之前可以先做一次O(n)扫描找最小值和最大值。如果 max - min k * (n - 1)那么可以直接输出-1不用排序。这个剪枝的依据是n个点排成一个序列相邻差的总和是首尾距离。首尾距离至少是 max - min。如果每段相邻差都不超过k那么首尾距离最多是 k*(n-1)。这个条件不满足说明无论怎么重排都不可能成功。实测中这个剪枝能省掉不少大数组的排序开销尤其是当最大值和最小值相差特别大时一秒钟都不用等就能返回结果。不过要注意这个条件只是必要条件不是充分条件。即使 max - min ≤ k*(n-1)排序后仍然可能有某个相邻差超过k该走的扫描步骤不能省。2.4 从结论到代码算法流程整体算法流程就三步读入 n、k 和数组 a。对 a 从小到大排序。遍历 i1 到 n-1如果 a[i] - a[i-1] k输出-1并结束否则继续。如果全部相邻差都不超过k输出排序后的数组。时间复杂度是 O(n log n)主要花在排序上空间复杂度 O(1)不算输入存储的话。这个复杂度在n10^5时非常安全在n10^6时需要稍微注意语言选择和IO性能后面会讲。3. Java、C、Python三套实现的细节对比3.1 Java版本Arrays.sort与输入输出的取舍Java的考场写法我推荐直接用Arrays.sort不要手写快排或归并。手写排序在笔试环境里除了给自己增加bug概率没有任何好处。标准库排序是双基准快排加插入排序的混合策略对基本类型数组性能很好。import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); long k Long.parseLong(st.nextToken()); long[] a new long[n]; st new StringTokenizer(br.readLine()); for (int i 0; i n; i) { a[i] Long.parseLong(st.nextToken()); } // 剪枝跨度过大直接失败 long min a[0], max a[0]; for (long v : a) { min Math.min(min, v); max Math.max(max, v); } if (max - min k * (n - 1)) { System.out.println(-1); return; } Arrays.sort(a); for (int i 1; i n; i) { if (a[i] - a[i - 1] k) { System.out.println(-1); return; } } StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { if (i 0) sb.append( ); sb.append(a[i]); } System.out.println(sb); } }这里有几个细节值得注意。一是用long而不是int因为数组元素可能是很大的整数做差值时int可能溢出导致判断错误。虽然很多网上的题解用int也能过但在真实笔试中这是非常容易被卡的一个点。二是我用了BufferedReader和StringTokenizer而不是Scanner。Scanner在处理10^5以上输入时性能明显偏慢很多学校的OJ上Scanner会直接TLE换成BufferedReader之后速度能快一个量级。三是在输出时用StringBuilder拼接避免反复调用System.out.print这也是一个常见性能优化点。3.2 C版本sort与读入优化C版本核心就是algorithm头文件里的sort时间复杂度同样是O(n log n)。C98、C11、C17在笔试环境中都能编译代码尽量写兼容性好的风格避免用到奇奇怪怪的语法特性。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin n k; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } long long mn a[0], mx a[0]; for (long long v : a) { mn min(mn, v); mx max(mx, v); } if (mx - mn k * (n - 1)) { cout -1 \n; return 0; } sort(a.begin(), a.end()); for (int i 1; i n; i) { if (a[i] - a[i - 1] k) { cout -1 \n; return 0; } } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }C最容易出问题的地方是ios::sync_with_stdio(false)和cin.tie(nullptr)必须写在读入之前。很多同学知道要加这两行但不知道它们的含义。默认情况下C的cin/cout和C的stdio是同步的目的是让混用cin和printf时不会乱序但这会带来额外性能开销。关掉同步之后cin/cout的速度就上来了接近scanf/printf。cin.tie(nullptr)是取消cin和cout的绑定避免每次输入前都强制刷新输出缓冲区。差值用long long也是必要的。如果用int当数组中有接近2e9的数且公差较大时减法会溢出成负数导致a[i] - a[i-1] k判断出错。这种隐蔽的坑很难在自测时发现因为小数据根本触发不了溢出。还有一个小的输出细节如果数组只有一个元素排序后直接输出即可我的循环在n1时会自然绕过检查并正确输出不需要特判。3.3 Python版本简洁但要注意读入性能Python的代码是所有版本中最短的因为sort和split都内置了。但Python在笔试环境里最容易翻车的是读入和输出性能尤其是当n超过10^5时用input()一行一行读会非常慢直接用sys.stdin.read()一次性读入是更稳妥的做法。import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) k int(data[1]) a list(map(int, data[2:2 n])) mn min(a) mx max(a) if mx - mn k * (n - 1): print(-1) return a.sort() for i in range(1, n): if a[i] - a[i - 1] k: print(-1) return sys.stdout.write( .join(map(str, a)) \n) if __name__ __main__: main()用sys.stdin.buffer.read()而不是sys.stdin.read()是个性能细节buffer版本读的是字节串再用split分割省去了编解码开销。map(str, a)配合 .join()是一次性构造输出字符串的常规做法比循环print快很多。Python版本有一个隐含的优势整数无上限不需要担心溢出。这也是为什么很多同学用Python突击刷题时遇到大数问题能快速AC的原因之一。但Python慢也是客观事实当n到10^6量级时纯Python的sort仍然可能压线这时候通常要换PyPy或者换C。3.4 三种语言对比与选型建议用一个表格直观对比三种实现的核心差异维度JavaCPython排序APIArrays.sortsortlist.sort读入方式BufferedReadercinsys.stdin.buffer.read慢速风险Scanner未关同步逐行input溢出风险int需要换longint需要换long long无输出性能StringBuildercout\n.join 或 .join代码量中等中等偏多最少如果笔试环境支持多种语言我的建议是追求极致的稳定性选C追求开发效率选PythonJava更适合在企业里已经长时间用Java、对标准库更熟悉的同学。不要把时间浪费在纠结语言上三种写法都能AC关键是逻辑想清楚。4. 边界用例与在线自测的正确姿势4.1 必须覆盖的边界用例算法题最容易栽在边界条件上。这道题我至少总结了下面几类必测用例建议写代码前先想清楚这些场景的输出测试场景输入示例预期输出n11 0 / 55k0且所有元素相等3 0 / 1 1 11 1 1k0但元素不全相等3 0 / 1 2 1-1全部相邻差刚好等于k4 1 / 1 2 3 41 2 3 4存在一对相邻差超过k4 1 / 1 2 3 10-1含负数3 3 / -5 -2 0-5 -2 0重复元素混合大间隔5 1 / 1 1 1 100 1-1剪枝生效的极端跨度5 1 / 0 0 0 0 100-1最后一条是剪枝逻辑最容易验证的用例max-min100k*(n-1)41004直接输出-1排序都不用跑。这条用例能帮你快速确认剪枝代码没有写反。n1的情况在三种语言里都要格外小心。Java版本里如果直接用a[0]初始化min和max没问题C的vector只有一个元素时循环边界也能正确跳过Python的range(1, n)在n1时是空循环也不会出错。但如果你在代码里写死了for (int i 0; i n - 1; i)当n1时n-10不会进入循环同样没问题。真正危险的是访问a[i1]时没有判断范围。4.2 本地自测脚本怎么写笔试时很多同学没有养成先自测的习惯直接提交结果就是WA得莫名其妙。我习惯在本地写一个简单的测试框架把样例输入喂给程序再对比输出。这里分享一个Python版的轻量自测脚本思路import subprocess import sys cases [ (1 0\n5\n, 5\n), (3 0\n1 1 1\n, 1 1 1\n), (3 0\n1 2 1\n, -1\n), (4 1\n1 2 3 4\n, 1 2 3 4\n), (4 1\n1 2 3 10\n, -1\n), ] for inp, expected in cases: p subprocess.run( [sys.executable, solution.py], inputinp.encode(), capture_outputTrue ) out p.stdout.decode().strip() exp expected.strip() status PASS if out exp else FAIL print(f{status}: input{inp!r}, expected{exp!r}, got{out!r})这种脚本只用来快速回归不需要做得很重。真正的压力测试可以写一个随机数据生成器生成n在10^5~10^6之间的数组验证程序不超时、不崩溃。随机数据生成器的核心逻辑很简单import random n 100000 k random.randint(0, 10**9) a [random.randint(-10**9, 10**9) for _ in range(n)] print(n, k) print( .join(map(str, a)))把它和solution.py通过管道连起来跑一次就能验证读入性能。如果你有写对拍器的经验也可以自己实现一个O(n^2)的暴力解作为基准在小数据上随机对拍确认排序版解法和暴力搜索结果一致。对拍是排查算法逻辑错误最有效的手段。4.3 在线的“测试”怎么找很多同学习惯在牛客网、AcWing、力扣上搜原题做在线评测。这道题由于是春招流传版本各家平台收录的题目描述可能略有差异但核心逻辑一样。我建议的做法是先把本地自测用例跑通再在各种刷题平台的“真题/面经”板块搜“阿里 春招 不稳定 相似”或“阿里巴巴 不稳定 or 相似”找到收录的题面后重点确认输入输出格式是否一致。有的平台要求多组数据有的只要求单组有的样例最后有换行有的没有。格式不一致会导致“本地AC、提交WA”的经典问题。如果找不到完全一样的题目也可以找一个输入输出格式类似的排序题作为替代验证排序API和读入写法是否有性能问题。题号不一定是固定的核心是把本文的本地自测流程跑熟真正到了考场上只需要改一下读入格式就能复用。5. 面试复盘这道题真正考察的底层能力5.1 “排序稳定性”这个基础概念为什么重要春招笔试出现“不稳定or相似”这种题名本质上是在考察基础概念和实际应用的结合能力。排序稳定性是一个被很多人忽略的知识点。大家背八股文时都知道快排不稳定、选择排序不稳定、堆排序不稳定但能把这几个结论的原因讲清楚的人不多能把它放进算法题里灵活运用的更少。这道题如果只看题名“不稳定”三个字会让人以为是考排序算法本身的稳定性。但真正的考点在于不稳定排序并不会改变排序后的数值序列它只改变相等元素的相对位置。如果读者对排序稳定性的理解只停留在“快排不稳定所以要背下来”这种层面遇到这道题就容易陷入手写各种排序的泥潭。我自己的体会是复习排序稳定性时不能只记结论要理解为什么。举个例子选择排序为什么不稳定因为每次选择最小值放到前面时可能把某个相等元素原本的相对顺序破坏掉。比如数组 [3, 3, 1]第一轮选到1放到最前面数组变成 [1, 3, 3]两个3的相对顺序没有变但如果是 [3, 3, 3, 1] 这样的结构某个位置的3被交换到后面的位置相对顺序就变了。理解了交换过程才能理解为什么有的排序稳定、有的不稳定。5.2 这道题和“不稳定排序”的真实工程联系虽然这道题里不稳定排序不影响答案但“不稳定”这个概念在真实开发中确实有应用场景。比如有个对象列表先按优先级排序再按时间排序如果第二轮的排序算法不稳定就可能破坏第一轮已经排好的优先级顺序。这也是为什么Java的Collections.sort对对象使用归并排序稳定而对基本类型使用双基准快排不稳定——因为对象常常有多个排序关键字稳定性能保证多关键字排序的正确性。延伸开来说这道题背后的“排序输出唯一性”在工程中同样重要。很多业务系统里要对数据做去重、邻居查找、区间合并前提都是先把数据排好序然后扫描相邻元素。相邻元素的差值问题本质上是一维空间里的聚类问题和“找出数组中最接近的一对数”“判断是否有两个数之差不超过k”是同一类。理解了这一层刷题就不只是为了AC而是真的在积累工程思维。5.3 遇到信息不完整或带误导性的题目该怎么办最后分享一个实战层面的建议。春招笔试题在流传过程中经常会出现描述不完整、版本不一致、甚至题名自带误导的情况。“不稳定or相似”这个题名就是很典型的一个例子。我的做法是拿到题目先花两分钟把题面翻译成自己能理解的数学表述划出三个关键信息——输入规模、判定条件、输出格式。如果题面里出现了像“不稳定”这种明显带有技术暗示的词先别急着往八股文方向联想先想清楚它对最终输出的影响是什么。这道题里“不稳定”对最终输出没有任何影响因为它不改变数值序列。如果考场上确实看不出正解可以先用暴力DFS验证小数据确认自己理解的题意是对的。然后从暴力的结果中找规律——比如把所有满足条件的排列打印出来观察它们是不是都能通过“排序后检查”来覆盖。这种从暴力到优化的思路是所有算法题通用的一条路径。我觉得这道题真正难得的不是那个排序结论本身而是它逼着你在一个带有迷惑性的题目里保持清醒把一个复杂问题简化成排序加扫描。这种能力比会背任何一种排序算法都更有价值。