1. 先把题目稳稳拿住题意拆解与隐藏考点1.1 一句话说清题目在做什么华为OD机试里100分题往往是整场考试的“定心丸”但也是翻车重灾区。就拿“整型数组按照个位数排序”这道题来说明面上就是一个取模加排序思路简单到让人想笑。可上了双机位的考场真正写完却有一半的人过不了隐藏用例。题目本质上是这样给你一个整型数组要求按每个元素的个位数从小到大重新排序当个位数相同时元素在输出里的相对顺序要和输入保持一致。举个例子输入[21, 32, 11, 41]先算出每个数的个位分别是1、2、1、1按个位升序归成两类个位1的有21、11、41个位2的只有一个32。因为要求相同个位保持原相对顺序所以21仍然排在11和41前面最终输出[21, 11, 41, 32]。这里就藏了第一个坑如果不要求稳定只按个位数排序那[21, 11, 41, 32]、[11, 41, 21, 32]、[41, 21, 11, 32]全都可以算“个位升序”。但OJ判题只会认一个答案所以题面大概率会写明“相同个位数保持原顺序”或者在样例里让你能看出相对顺序不能变。读题的时候一定要把这句话圈出来。1.2 这道题的三个隐藏考点按我看到的错误案例90%的人能在半分钟内想到“取模比较”这个核心思路但真正一次写对的人不到一半。三个容易出问题的地方几乎个个都是送命题。第一个是负数个位数的处理。正整数直接% 10没问题但Java里取余运算的符号是和被除数保持一致的-23 % 10结果是-3不是3。如果不处理负数会被排到最前面整个顺序全乱。第二个是排序稳定性。Arrays.sort(int[]) 底层是双轴快速排序不稳定而且基本类型数组还不支持传Comparator你没法直接在 int[] 上指定“按个位数比较”。第三个是输出格式。很多OD题目对空格、换行比较敏感行尾多一个空格有时就直接判错。这三个点单独拿出来都不难但凑在一起就能筛掉一大批只背过API、没真正写过排序代码的人。1.3 100分题在整场考试里处于什么位置华为OD机试的试卷通常有梯度大致的套路是基础题保底、中等题拉开差距、难题用来筛高分。100分题就是那种“基本盘”正常备考过的人应该在5到10分钟内完整AC而且要保证所有用例全过不能只过公开样例。这类题不会考动态规划、图论这些重算法考的是Java基础功底集合框架熟不熟、Comparator怎么写、边界条件全不全。说句实在话很多刷过几百道力扣的人反而在这类题上翻车因为“简单题”让人本能地放松警惕读题一目十行把稳定性要求漏得干干净净。C卷是OD机试里比较常见的试卷代号你用Java答题考察的就是Java语法和常用API的熟练度。双机位则意味着电脑摄像头加手机侧后方摄像头同时监控这种环境下你没法临时翻资料、查API所以平时习惯靠IDE补全提示的同学上机前一定要刻意练几次“裸写”。2. 个位数排序的三种落地写法2.1 写法一十个桶分组后依次输出我最早做这道题时用的是最不需要动脑子的写法开十个桶。因为个位数只可能是0到9遍历数组时把每个数塞进对应个位的桶里最后从0号桶到9号桶依次把元素倒出来。这个过程的稳定性是天然保证的——同一个桶里的元素是遍历原数组时按顺序追加进去的顺序不会乱。完整代码大概是这个样子import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); ListListInteger buckets new ArrayList(); for (int i 0; i 10; i) { buckets.add(new ArrayList()); } for (int i 0; i n; i) { int x sc.nextInt(); int digit Math.abs(x % 10); buckets.get(digit).add(x); } boolean first true; for (int d 0; d 10; d) { for (int val : buckets.get(d)) { if (!first) { System.out.print( ); } System.out.print(val); first false; } } System.out.println(); } }注意这里不能图省事写ListInteger[] buckets new ArrayList[10]Java的泛型数组是禁止直接创建的编译会报“generic array creation”错误。就算用裸类型强行绕过也会留编译警告在考场上没必要给自己埋雷老老实实用ListListInteger。这种桶排序的时间复杂度是O(n)比基于比较的排序还快而且完全不需要理解排序算法的稳定性。我个人认为这是考场最稳的解法逻辑直白几乎不存在写错Comparator的可能。2.2 写法二稳定排序 自定义比较器如果你平时写集合排序更顺手也可以用第二种写法。核心思路是把数组转成ListInteger然后用List.sort配合自定义比较器。关键点是Java对对象排序用的归并排序/TimSort是稳定的所以Comparator里只需要处理“谁的个位数大”个位数相等时返回0剩下的相对顺序交给排序算法去保。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); ListInteger nums new ArrayList(); for (int i 0; i n; i) { nums.add(sc.nextInt()); } nums.sort((a, b) - Integer.compare(Math.abs(a % 10), Math.abs(b % 10))); // 等价写法nums.sort(Comparator.comparingInt(x - Math.abs(x % 10))); for (int i 0; i n; i) { if (i 0) { System.out.print( ); } System.out.print(nums.get(i)); } System.out.println(); } }这里有两个细节值得讲。第一个是nums必须是ListInteger不能是int[]。基本类型数组没有sort(Comparator)的重载你没法给它指定比较规则所以必须先转成包装类型集合。第二个是Math.abs(x % 10)这个写法而不是Math.abs(x) % 10——这两个在极值情况下有本质区别下一章专门展开。Comparator.comparingInt的写法更短本质是把“提取排序键”和“比较”两步拆开先取每个数的个位数绝对值再用Integer.compare去比较。理解了这个等价关系用哪个版本都行。2.3 写法三一行流的简约版如果你平时写Java 8流式编程比较多可能会想用Stream一行搞定int[] result Arrays.stream(nums) .boxed() .sorted(Comparator.comparingInt(x - Math.abs(x % 10))) .mapToInt(Integer::intValue) .toArray();这版写法很优雅但坑也不少。第一你必须先.boxed()把IntStream转成StreamInteger因为IntStream没有接收Comparator的sorted方法。第二不要在map阶段就把原数变成个位数。如果你写Arrays.stream(nums).map(x - Math.abs(x % 10)).sorted()排序的对象已经是个位数序列了最后toArray得到的是一串个位数而不是原数组。第三流式sorted同样是稳定排序这一点不用担心但正因为流写法叠加了boxing、map、toArray三层转换考场出错率明显更高。我的建议是这版留着平时练习理解原理可以考场上别用。100分题要的是稳不是秀。2.4 三种写法怎么选维度桶排序List 稳定排序Stream流式代码量中等少最少稳定性理解成本不需要天然稳定需要知道算法稳定需要知道流排序稳定时间复杂度O(n)O(n log n)够用O(n log n)够用考场翻车风险低低偏高复用性一般高中我个人建议练习题阶段把桶排序和稳定排序各写一遍考场上用第二种。因为写List排序时你会自然地关注Comparator怎么写、稳定性从哪来这种思路离大多数机试题的正常观察更近桶排序虽然在这个题里很稳但换一个“按字符串长度排序”的变体就没法直接套了。3. 极易翻车的边界用例与根因分析3.1 负数个位数到底怎么取如果输入里出现负数直接写x % 10就会出错。Java的取余运算结果和左边操作数符号一致-123 % 10得到-3而题目要的比较基准是“个位数字”也就是数学意义上的3。我构造一个直观的例子输入[9, -67, 45, -123]。如果不对负数做处理四个数的“个位”按x % 10算出来是9、-7、5、-3排序结果会变成[-67, -123, 45, 9]整个顺序完全是错的。正确做法是对取模结果再做绝对值也就是Math.abs(x % 10)。这样四位数对应的排序键变成9、7、5、3升序输出[-123, 45, -67, 9]。也许你会想题目不是“整型数组”吗也没说一定包含负数啊。但考场上你永远不知道隐藏用例长什么样与其赌输入范围不如把写法本身做稳。加一个Math.abs的成本几乎为零收益是直接消灭一整类错误。3.2 Math.abs(Integer.MIN_VALUE) 溢出陷阱这一节是我特别想拿出来单独说的因为这是个真正“看着对、实际错”的经典案例。很多人在处理负数时会自然地写Math.abs(x) % 10但Integer.MIN_VALUE恰好是这段逻辑的杀手。Java中int的范围是-2147483648到2147483647正方向没有和-2147483648对应的值。所以Math.abs(Integer.MIN_VALUE)的结果依然是-2147483648取绝对值并没有变成正数。于是int x Integer.MIN_VALUE; System.out.println(Math.abs(x) % 10); // 输出 -8而不是 8这个错误非常隐蔽。如果数组里恰好有Integer.MIN_VALUE它的排序键会被算成 -8直接排到最前面并且很难通过肉眼观察定位原因。而正确的Math.abs(x % 10)就不会有这个问题因为x % 10的取值范围只有 -9到9对这样一个范围内的数做绝对值永远不会溢出。这种极端值在机试用例里未必会出现但我想强调的是写代码不能只求“样例能过”要能说出每一步写法为什么安全。面试官如果顺着这道题追问一句“负数怎么处理”你能答出Math.abs(x % 10)和Math.abs(x) % 10的区别就是一个很不错的加分点。3.3 为什么不能用减法差值比较有人图省事会这么写nums.sort((a, b) - Math.abs(a % 10) - Math.abs(b % 10));在这个题目里个位数差值的范围只有 -9到9减法的确不会溢出所以它“碰巧”能过。但我非常不建议养成这种习惯。Comparator的约定是返回负值、零、正值用减法来表达比较逻辑语义并不直观一旦排序键从“个位数”变成“最后两位”或者某种组合字段减法就可能因为整数溢出产生完全错误的结果。规范的写法是nums.sort((a, b) - Integer.compare(Math.abs(a % 10), Math.abs(b % 10)));Integer.compare把“小于、等于、大于”三种关系表达得清清楚楚也彻底规避了溢出问题。为什么我在这道简单题上反复强调这一点因为机试判题时错误答案并不关心你错在哪一行但你自己要知道错在哪里才能在下一次避免。把Comparator的写法固化到肌肉记忆里比依赖“碰巧溢出不了”靠谱得多。3.4 空输入、单元素、大数量输入的测试清单写完核心逻辑后我习惯按下面的用例清单自测一遍。这里也分享给你用例类型输入期望输出空数组第一行0没有第二行输出空行不崩溃单个元素1然后一个数原样输出全部相同个位数3个数个位都是1按原顺序输出包含负数9 -67 45 -123-123 45 -67 9整数极值2147483647 -2147483648 0对应个位7、8、0输出0 2147483647 -2147483648关于输入解析还有一个常见分歧有的题目第一行给N第二行给数组有的题目没有N直接给一行数字。我建议用循环读取而不是强依赖第一行NScanner sc new Scanner(System.in); ListInteger nums new ArrayList(); while (sc.hasNextInt()) { nums.add(sc.nextInt()); }这种写法能同时兼容两种输入格式也不会因为数组末尾多一个空格或多一行空行而断掉。当然如果题目明确要求第一行必须是N后面还要读取其他输入那就按题面来但至少你要意识到“读输入”本身也有边界问题。4. 稳定排序原理这道题真正的考点4.1 什么是稳定排序如果只看代码这道题写的好像只是“取模比较”。但“相同个位数保持原顺序”这句话其实直接指向了排序算法里一个很重要的概念稳定性。稳定排序的定义是如果两个元素的排序键相等排序后它们的相对位置保持不变。举个生活化的例子假设你有一份按学号排好的学生名单现在要按成绩重新排序。稳定排序之后相同成绩的学生之间仍然保持着学号从小到大的顺序不稳定排序则可能把这份“学号顺序”打乱。回到这道题个位数相等就是“键相等”原数组中的先后顺序就是“相对位置”题目要求的“保持原顺序”翻译过来就是四个字使用稳定排序。有人可能会问如果题目没写“保持原顺序”怎么办我的建议是仍然按稳定排序处理。因为OJ判题需要答案唯一如果题面没有约束多个合法答案之间就没法判定所以大多数这类题要么明说、要么用样例暗示稳定要求。按稳定排序做至少不会错。4.2 Java里哪些排序天生稳定Java的排序API稳定性并不是统一的我整理了一张表排序调用底层算法是否稳定Collections.sort(List)归并排序 / TimSort稳定List.sort(Comparator)归并排序 / TimSort稳定Arrays.sort(Object[])TimSort稳定Arrays.sort(int[])双轴快速排序不稳定Stream.sorted()稳定排序稳定这里就产生了一个很尴尬的局面题目读入的是int[]而Arrays.sort(int[])既不稳定又不支持传Comparator所以直连数组的方案直接走不通。要么你转成ListInteger借助稳定排序要么自己用桶排序保证稳定。这也是为什么前面给了两种截然不同的解法——它们解决同一个问题的路径不一样但都绕开了这个限制。我顺便解释一下底层逻辑JDK设计者认为基本类型元素的顺序没有“身份”差异排序后谁在前谁在后无关紧要所以用了速度更快的快排而对象排序默认稳定因为对象可能携带业务信息很多场景需要保留原始顺序。这是工程上的权衡不是随意实现的。4.3 面试官顺着这道题可能追问的三个方向这类100分题简单归简单但它的考点可以延伸。如果你准备面试建议把下面三个追问也想清楚第一个追问不用Comparator你能写出一个稳定排序吗桶排序就是典型回答。按个位数分成10个桶从0到9按顺序输出时间复杂度O(n)不需要比较器稳定性天然保证。这道题的“桶写法”其实就是一次基数排序中按个位分配的过程。第二个追问为什么要求稳定排序时不用快速排序因为快速排序在交换元素时可能改变相等元素的相对顺序常见实现是不稳定的。除非用特定的复杂度很高的改动否则快排本身不承诺稳定。归并排序稳定的根源在于它只做相邻区间的合并不跨距离交换元素。第三个追问如果把“个位数”换成“十位数”或者“最后两位”思路变吗基本不变只是把% 10换成% 100或者写成Math.abs(x) / 10 % 10。这个变体再往外延伸其实就是在一步一步接近基数排序的思路——先按低位排再按高位排。能在考场上想到这一层说明你对排序机制的理解不是背API而是真的懂了。5. 机考实战双机位下的调试与提交节奏5.1 拿到题目后的标准操作流程双机位考试和平时自己刷题最大的区别是心态和环境但操作流程应该是固化的。我每次拿到题目都按五步走第一步读题两遍。第一遍快速过第二遍把输入格式、输出要求、排序规则圈出来。像这道题我圈的就是“从小到大”“个位数”“保持原相对顺序”。第二步别急着开写先在草稿纸上把题面样例手算一遍。手算的过程会逼你确认“相同个位数保持顺序”具体是怎么体现的这一步看似浪费时间实际能拦下大量低级错误。第三步写主流程骨架先读入、再排序、最后输出骨架跑通之后再补边界。第四步跑样例和自己设计的自测用例。第五步确认没有多余的调试输出再提交。双机位的附加约束是你不能开浏览器搜索不能翻本地笔记甚至连低头看手机都不行。所以平时练习就要把自己当“裸考”——写完代码不要靠IDE自动修复来纠正尽量训练一次编译通过的准确率。至少Math.abs、Integer.compare、Comparator.comparingInt、Scanner这套高频API要做到闭着眼都能写对。5.2 自测用例怎么设计我常跟人说机试拼的不是会不会写而是能不能一次写对。一次写对的底气来自自测用例的设计。我一般至少跑四类题面示例用来确认基本理解正确。全部相同个位数的用例用来验证稳定性。包含负数的用例用来验证取模处理。单元素和空数组用来验证边界不崩。如果时间充裕我还会构造一个10万个随机数的大数组重点不是看输出对不对而是看程序是否能快速跑完。10万规模下O(n log n)的排序是毫秒级完成如果明显卡顿说明复杂度可能出了问题。比如有人一着急用了冒泡排序十万个数的平方级复杂度在机试环境里就是漫长的等待一旦超时整个题都白做。输出格式也要在意。我的习惯是写一个统一的打印逻辑元素之间打空格最后一个元素后只换行、不补空格。不要在多个分支里各自写一套输出代码否则很容易出现样例输出末尾多了一个空格的情况。很多OJ对行尾空格敏感这一点丢分最冤。5.3 常见失误与复盘方法这题的失误类型其实很固定我按出现频率排一下漏读稳定性要求。最致命而且有时样例恰好不包含相同个位数的元素你根本发现不了问题直接提交才被判错。负数取模没有做绝对值处理。错误结果整体乱序一眼就能看出来但写代码时就是想不起来。想直接用Arrays.sort(int[])然后发现基本类型数组不能传Comparator白白耽误时间。Stream流式写法中map错了对象最后输出变成了一串个位数。输入解析没有兼容多空格或空行用了强依赖固定格式的读取方式。复盘时我会把这些错误按类型记下来而不是简单把正确答案抄一遍。错因分类之后你会发现OD机试100分题的考点高度重复取模、字符串、数组模拟、简单排序、输入输出格式。每类积累三到五条易错点后面再遇到同类题基本就能条件反射地避开。5.4 个人习惯最后30秒的检查法文章最后分享一个我自己的小习惯。无论题目看起来多简单提交前我都会花30秒重读一遍题面专门对照两个点稳定性要求有没有体现在代码里输出格式是不是和题目完全一致。这道整型数组按个位数排序的题表面就是一次% 10取模实际却把稳定排序、Java集合API、负数边界、输入输出规范全部串了一遍。把它彻底吃透你在华为OD机试里拿下的第一个100分大概率就是这一类题。祝考试顺利一次AC。
华为OD机试：整型数组按个位数排序的Java稳定排序解法
1. 先把题目稳稳拿住题意拆解与隐藏考点1.1 一句话说清题目在做什么华为OD机试里100分题往往是整场考试的“定心丸”但也是翻车重灾区。就拿“整型数组按照个位数排序”这道题来说明面上就是一个取模加排序思路简单到让人想笑。可上了双机位的考场真正写完却有一半的人过不了隐藏用例。题目本质上是这样给你一个整型数组要求按每个元素的个位数从小到大重新排序当个位数相同时元素在输出里的相对顺序要和输入保持一致。举个例子输入[21, 32, 11, 41]先算出每个数的个位分别是1、2、1、1按个位升序归成两类个位1的有21、11、41个位2的只有一个32。因为要求相同个位保持原相对顺序所以21仍然排在11和41前面最终输出[21, 11, 41, 32]。这里就藏了第一个坑如果不要求稳定只按个位数排序那[21, 11, 41, 32]、[11, 41, 21, 32]、[41, 21, 11, 32]全都可以算“个位升序”。但OJ判题只会认一个答案所以题面大概率会写明“相同个位数保持原顺序”或者在样例里让你能看出相对顺序不能变。读题的时候一定要把这句话圈出来。1.2 这道题的三个隐藏考点按我看到的错误案例90%的人能在半分钟内想到“取模比较”这个核心思路但真正一次写对的人不到一半。三个容易出问题的地方几乎个个都是送命题。第一个是负数个位数的处理。正整数直接% 10没问题但Java里取余运算的符号是和被除数保持一致的-23 % 10结果是-3不是3。如果不处理负数会被排到最前面整个顺序全乱。第二个是排序稳定性。Arrays.sort(int[]) 底层是双轴快速排序不稳定而且基本类型数组还不支持传Comparator你没法直接在 int[] 上指定“按个位数比较”。第三个是输出格式。很多OD题目对空格、换行比较敏感行尾多一个空格有时就直接判错。这三个点单独拿出来都不难但凑在一起就能筛掉一大批只背过API、没真正写过排序代码的人。1.3 100分题在整场考试里处于什么位置华为OD机试的试卷通常有梯度大致的套路是基础题保底、中等题拉开差距、难题用来筛高分。100分题就是那种“基本盘”正常备考过的人应该在5到10分钟内完整AC而且要保证所有用例全过不能只过公开样例。这类题不会考动态规划、图论这些重算法考的是Java基础功底集合框架熟不熟、Comparator怎么写、边界条件全不全。说句实在话很多刷过几百道力扣的人反而在这类题上翻车因为“简单题”让人本能地放松警惕读题一目十行把稳定性要求漏得干干净净。C卷是OD机试里比较常见的试卷代号你用Java答题考察的就是Java语法和常用API的熟练度。双机位则意味着电脑摄像头加手机侧后方摄像头同时监控这种环境下你没法临时翻资料、查API所以平时习惯靠IDE补全提示的同学上机前一定要刻意练几次“裸写”。2. 个位数排序的三种落地写法2.1 写法一十个桶分组后依次输出我最早做这道题时用的是最不需要动脑子的写法开十个桶。因为个位数只可能是0到9遍历数组时把每个数塞进对应个位的桶里最后从0号桶到9号桶依次把元素倒出来。这个过程的稳定性是天然保证的——同一个桶里的元素是遍历原数组时按顺序追加进去的顺序不会乱。完整代码大概是这个样子import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); ListListInteger buckets new ArrayList(); for (int i 0; i 10; i) { buckets.add(new ArrayList()); } for (int i 0; i n; i) { int x sc.nextInt(); int digit Math.abs(x % 10); buckets.get(digit).add(x); } boolean first true; for (int d 0; d 10; d) { for (int val : buckets.get(d)) { if (!first) { System.out.print( ); } System.out.print(val); first false; } } System.out.println(); } }注意这里不能图省事写ListInteger[] buckets new ArrayList[10]Java的泛型数组是禁止直接创建的编译会报“generic array creation”错误。就算用裸类型强行绕过也会留编译警告在考场上没必要给自己埋雷老老实实用ListListInteger。这种桶排序的时间复杂度是O(n)比基于比较的排序还快而且完全不需要理解排序算法的稳定性。我个人认为这是考场最稳的解法逻辑直白几乎不存在写错Comparator的可能。2.2 写法二稳定排序 自定义比较器如果你平时写集合排序更顺手也可以用第二种写法。核心思路是把数组转成ListInteger然后用List.sort配合自定义比较器。关键点是Java对对象排序用的归并排序/TimSort是稳定的所以Comparator里只需要处理“谁的个位数大”个位数相等时返回0剩下的相对顺序交给排序算法去保。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); ListInteger nums new ArrayList(); for (int i 0; i n; i) { nums.add(sc.nextInt()); } nums.sort((a, b) - Integer.compare(Math.abs(a % 10), Math.abs(b % 10))); // 等价写法nums.sort(Comparator.comparingInt(x - Math.abs(x % 10))); for (int i 0; i n; i) { if (i 0) { System.out.print( ); } System.out.print(nums.get(i)); } System.out.println(); } }这里有两个细节值得讲。第一个是nums必须是ListInteger不能是int[]。基本类型数组没有sort(Comparator)的重载你没法给它指定比较规则所以必须先转成包装类型集合。第二个是Math.abs(x % 10)这个写法而不是Math.abs(x) % 10——这两个在极值情况下有本质区别下一章专门展开。Comparator.comparingInt的写法更短本质是把“提取排序键”和“比较”两步拆开先取每个数的个位数绝对值再用Integer.compare去比较。理解了这个等价关系用哪个版本都行。2.3 写法三一行流的简约版如果你平时写Java 8流式编程比较多可能会想用Stream一行搞定int[] result Arrays.stream(nums) .boxed() .sorted(Comparator.comparingInt(x - Math.abs(x % 10))) .mapToInt(Integer::intValue) .toArray();这版写法很优雅但坑也不少。第一你必须先.boxed()把IntStream转成StreamInteger因为IntStream没有接收Comparator的sorted方法。第二不要在map阶段就把原数变成个位数。如果你写Arrays.stream(nums).map(x - Math.abs(x % 10)).sorted()排序的对象已经是个位数序列了最后toArray得到的是一串个位数而不是原数组。第三流式sorted同样是稳定排序这一点不用担心但正因为流写法叠加了boxing、map、toArray三层转换考场出错率明显更高。我的建议是这版留着平时练习理解原理可以考场上别用。100分题要的是稳不是秀。2.4 三种写法怎么选维度桶排序List 稳定排序Stream流式代码量中等少最少稳定性理解成本不需要天然稳定需要知道算法稳定需要知道流排序稳定时间复杂度O(n)O(n log n)够用O(n log n)够用考场翻车风险低低偏高复用性一般高中我个人建议练习题阶段把桶排序和稳定排序各写一遍考场上用第二种。因为写List排序时你会自然地关注Comparator怎么写、稳定性从哪来这种思路离大多数机试题的正常观察更近桶排序虽然在这个题里很稳但换一个“按字符串长度排序”的变体就没法直接套了。3. 极易翻车的边界用例与根因分析3.1 负数个位数到底怎么取如果输入里出现负数直接写x % 10就会出错。Java的取余运算结果和左边操作数符号一致-123 % 10得到-3而题目要的比较基准是“个位数字”也就是数学意义上的3。我构造一个直观的例子输入[9, -67, 45, -123]。如果不对负数做处理四个数的“个位”按x % 10算出来是9、-7、5、-3排序结果会变成[-67, -123, 45, 9]整个顺序完全是错的。正确做法是对取模结果再做绝对值也就是Math.abs(x % 10)。这样四位数对应的排序键变成9、7、5、3升序输出[-123, 45, -67, 9]。也许你会想题目不是“整型数组”吗也没说一定包含负数啊。但考场上你永远不知道隐藏用例长什么样与其赌输入范围不如把写法本身做稳。加一个Math.abs的成本几乎为零收益是直接消灭一整类错误。3.2 Math.abs(Integer.MIN_VALUE) 溢出陷阱这一节是我特别想拿出来单独说的因为这是个真正“看着对、实际错”的经典案例。很多人在处理负数时会自然地写Math.abs(x) % 10但Integer.MIN_VALUE恰好是这段逻辑的杀手。Java中int的范围是-2147483648到2147483647正方向没有和-2147483648对应的值。所以Math.abs(Integer.MIN_VALUE)的结果依然是-2147483648取绝对值并没有变成正数。于是int x Integer.MIN_VALUE; System.out.println(Math.abs(x) % 10); // 输出 -8而不是 8这个错误非常隐蔽。如果数组里恰好有Integer.MIN_VALUE它的排序键会被算成 -8直接排到最前面并且很难通过肉眼观察定位原因。而正确的Math.abs(x % 10)就不会有这个问题因为x % 10的取值范围只有 -9到9对这样一个范围内的数做绝对值永远不会溢出。这种极端值在机试用例里未必会出现但我想强调的是写代码不能只求“样例能过”要能说出每一步写法为什么安全。面试官如果顺着这道题追问一句“负数怎么处理”你能答出Math.abs(x % 10)和Math.abs(x) % 10的区别就是一个很不错的加分点。3.3 为什么不能用减法差值比较有人图省事会这么写nums.sort((a, b) - Math.abs(a % 10) - Math.abs(b % 10));在这个题目里个位数差值的范围只有 -9到9减法的确不会溢出所以它“碰巧”能过。但我非常不建议养成这种习惯。Comparator的约定是返回负值、零、正值用减法来表达比较逻辑语义并不直观一旦排序键从“个位数”变成“最后两位”或者某种组合字段减法就可能因为整数溢出产生完全错误的结果。规范的写法是nums.sort((a, b) - Integer.compare(Math.abs(a % 10), Math.abs(b % 10)));Integer.compare把“小于、等于、大于”三种关系表达得清清楚楚也彻底规避了溢出问题。为什么我在这道简单题上反复强调这一点因为机试判题时错误答案并不关心你错在哪一行但你自己要知道错在哪里才能在下一次避免。把Comparator的写法固化到肌肉记忆里比依赖“碰巧溢出不了”靠谱得多。3.4 空输入、单元素、大数量输入的测试清单写完核心逻辑后我习惯按下面的用例清单自测一遍。这里也分享给你用例类型输入期望输出空数组第一行0没有第二行输出空行不崩溃单个元素1然后一个数原样输出全部相同个位数3个数个位都是1按原顺序输出包含负数9 -67 45 -123-123 45 -67 9整数极值2147483647 -2147483648 0对应个位7、8、0输出0 2147483647 -2147483648关于输入解析还有一个常见分歧有的题目第一行给N第二行给数组有的题目没有N直接给一行数字。我建议用循环读取而不是强依赖第一行NScanner sc new Scanner(System.in); ListInteger nums new ArrayList(); while (sc.hasNextInt()) { nums.add(sc.nextInt()); }这种写法能同时兼容两种输入格式也不会因为数组末尾多一个空格或多一行空行而断掉。当然如果题目明确要求第一行必须是N后面还要读取其他输入那就按题面来但至少你要意识到“读输入”本身也有边界问题。4. 稳定排序原理这道题真正的考点4.1 什么是稳定排序如果只看代码这道题写的好像只是“取模比较”。但“相同个位数保持原顺序”这句话其实直接指向了排序算法里一个很重要的概念稳定性。稳定排序的定义是如果两个元素的排序键相等排序后它们的相对位置保持不变。举个生活化的例子假设你有一份按学号排好的学生名单现在要按成绩重新排序。稳定排序之后相同成绩的学生之间仍然保持着学号从小到大的顺序不稳定排序则可能把这份“学号顺序”打乱。回到这道题个位数相等就是“键相等”原数组中的先后顺序就是“相对位置”题目要求的“保持原顺序”翻译过来就是四个字使用稳定排序。有人可能会问如果题目没写“保持原顺序”怎么办我的建议是仍然按稳定排序处理。因为OJ判题需要答案唯一如果题面没有约束多个合法答案之间就没法判定所以大多数这类题要么明说、要么用样例暗示稳定要求。按稳定排序做至少不会错。4.2 Java里哪些排序天生稳定Java的排序API稳定性并不是统一的我整理了一张表排序调用底层算法是否稳定Collections.sort(List)归并排序 / TimSort稳定List.sort(Comparator)归并排序 / TimSort稳定Arrays.sort(Object[])TimSort稳定Arrays.sort(int[])双轴快速排序不稳定Stream.sorted()稳定排序稳定这里就产生了一个很尴尬的局面题目读入的是int[]而Arrays.sort(int[])既不稳定又不支持传Comparator所以直连数组的方案直接走不通。要么你转成ListInteger借助稳定排序要么自己用桶排序保证稳定。这也是为什么前面给了两种截然不同的解法——它们解决同一个问题的路径不一样但都绕开了这个限制。我顺便解释一下底层逻辑JDK设计者认为基本类型元素的顺序没有“身份”差异排序后谁在前谁在后无关紧要所以用了速度更快的快排而对象排序默认稳定因为对象可能携带业务信息很多场景需要保留原始顺序。这是工程上的权衡不是随意实现的。4.3 面试官顺着这道题可能追问的三个方向这类100分题简单归简单但它的考点可以延伸。如果你准备面试建议把下面三个追问也想清楚第一个追问不用Comparator你能写出一个稳定排序吗桶排序就是典型回答。按个位数分成10个桶从0到9按顺序输出时间复杂度O(n)不需要比较器稳定性天然保证。这道题的“桶写法”其实就是一次基数排序中按个位分配的过程。第二个追问为什么要求稳定排序时不用快速排序因为快速排序在交换元素时可能改变相等元素的相对顺序常见实现是不稳定的。除非用特定的复杂度很高的改动否则快排本身不承诺稳定。归并排序稳定的根源在于它只做相邻区间的合并不跨距离交换元素。第三个追问如果把“个位数”换成“十位数”或者“最后两位”思路变吗基本不变只是把% 10换成% 100或者写成Math.abs(x) / 10 % 10。这个变体再往外延伸其实就是在一步一步接近基数排序的思路——先按低位排再按高位排。能在考场上想到这一层说明你对排序机制的理解不是背API而是真的懂了。5. 机考实战双机位下的调试与提交节奏5.1 拿到题目后的标准操作流程双机位考试和平时自己刷题最大的区别是心态和环境但操作流程应该是固化的。我每次拿到题目都按五步走第一步读题两遍。第一遍快速过第二遍把输入格式、输出要求、排序规则圈出来。像这道题我圈的就是“从小到大”“个位数”“保持原相对顺序”。第二步别急着开写先在草稿纸上把题面样例手算一遍。手算的过程会逼你确认“相同个位数保持顺序”具体是怎么体现的这一步看似浪费时间实际能拦下大量低级错误。第三步写主流程骨架先读入、再排序、最后输出骨架跑通之后再补边界。第四步跑样例和自己设计的自测用例。第五步确认没有多余的调试输出再提交。双机位的附加约束是你不能开浏览器搜索不能翻本地笔记甚至连低头看手机都不行。所以平时练习就要把自己当“裸考”——写完代码不要靠IDE自动修复来纠正尽量训练一次编译通过的准确率。至少Math.abs、Integer.compare、Comparator.comparingInt、Scanner这套高频API要做到闭着眼都能写对。5.2 自测用例怎么设计我常跟人说机试拼的不是会不会写而是能不能一次写对。一次写对的底气来自自测用例的设计。我一般至少跑四类题面示例用来确认基本理解正确。全部相同个位数的用例用来验证稳定性。包含负数的用例用来验证取模处理。单元素和空数组用来验证边界不崩。如果时间充裕我还会构造一个10万个随机数的大数组重点不是看输出对不对而是看程序是否能快速跑完。10万规模下O(n log n)的排序是毫秒级完成如果明显卡顿说明复杂度可能出了问题。比如有人一着急用了冒泡排序十万个数的平方级复杂度在机试环境里就是漫长的等待一旦超时整个题都白做。输出格式也要在意。我的习惯是写一个统一的打印逻辑元素之间打空格最后一个元素后只换行、不补空格。不要在多个分支里各自写一套输出代码否则很容易出现样例输出末尾多了一个空格的情况。很多OJ对行尾空格敏感这一点丢分最冤。5.3 常见失误与复盘方法这题的失误类型其实很固定我按出现频率排一下漏读稳定性要求。最致命而且有时样例恰好不包含相同个位数的元素你根本发现不了问题直接提交才被判错。负数取模没有做绝对值处理。错误结果整体乱序一眼就能看出来但写代码时就是想不起来。想直接用Arrays.sort(int[])然后发现基本类型数组不能传Comparator白白耽误时间。Stream流式写法中map错了对象最后输出变成了一串个位数。输入解析没有兼容多空格或空行用了强依赖固定格式的读取方式。复盘时我会把这些错误按类型记下来而不是简单把正确答案抄一遍。错因分类之后你会发现OD机试100分题的考点高度重复取模、字符串、数组模拟、简单排序、输入输出格式。每类积累三到五条易错点后面再遇到同类题基本就能条件反射地避开。5.4 个人习惯最后30秒的检查法文章最后分享一个我自己的小习惯。无论题目看起来多简单提交前我都会花30秒重读一遍题面专门对照两个点稳定性要求有没有体现在代码里输出格式是不是和题目完全一致。这道整型数组按个位数排序的题表面就是一次% 10取模实际却把稳定排序、Java集合API、负数边界、输入输出规范全部串了一遍。把它彻底吃透你在华为OD机试里拿下的第一个100分大概率就是这一类题。祝考试顺利一次AC。
