数组最大最小元素交换为何不能分开写？Java实现与边界分析

1. 题目拆解两个“交换”为什么不能分开写先把这个题目的需求说清楚。输入一个数组做两件事第一件把数组里最大的元素和第一个元素交换位置第二件把数组里最小的元素和最后一个元素交换位置然后把处理后的数组输出。这类题目在大学Java课程练习、笔试机考、甚至面试现场手写代码环节都很常见看起来就是基础数组操作但每次我遇到有人在这道题上翻车几乎都翻在同一个地方——两次交换之间的互相干扰。先说正常情况。假设输入是{5, 3, 8, 1, 9, 2}最大元素是9在索引4的位置最小元素是1在索引3的位置。第一步把9和第一个元素5交换得到{9, 3, 8, 1, 5, 2}第二步把1和最后一个元素2交换得到{9, 3, 8, 2, 5, 1}。顺理成章没有任何问题。但如果输入是{1, 2, 3, 4, 5}呢最大元素5在最后一个位置最小元素1在第一个位置这是一个极端但也非常常见的输入形态。很多初学者会这样写逻辑先找到最大值索引和最小值索引然后执行swap(arr, 0, maxIndex)和swap(arr, length-1, minIndex)。听着没毛病但实际跑一遍就露馅了——第一次交换让数组变成了{5, 2, 3, 4, 1}原来的最小值1已经被挪到了最后一位可你手里记录的minIndex还是0第二次交换会再次动用arr[0]数组就会被换回{1, 2, 3, 4, 5}。等于啥也没干。问题出在哪出在两个交换不是独立的。第二次交换要找的“最小值”在第一次交换完成后可能已经不在原来的位置了。如果最小值恰好位于第一个元素第一次“最大值换首元素”的动作会顺带把最小值一起搬走。这是整道题唯一的核心难点也是面试官最喜欢看候选人能不能提前意识到的点。除了上面那种“最小在首、最大在尾”的极端组合还有几种边界形态值得提前列出来最大值本身就在首元素第一步交换其实是自交换最小值本身就在尾元素第二步交换也是自交换数组里所有元素都相等两个“最大”“最小”指向同一个位置交换没有实际意义数组长度只有1甚至为空题目条件不满足应该直接跳过。这些情况如果在写代码前没想清楚写出来的代码总会漏掉其中一两种测试一多就挂。把这个坑理解透后面所有实现方案的取舍都围绕它展开。2. 三种实现方案从二次扫描到一次扫描的演进2.1 方案一二次扫描每次交换前重新找索引最不容易写错的办法是不要妄图一次遍历把最大最小都记下来然后用两次交换硬套而是老老实实分阶段处理先扫描整个数组找到最大值索引做第一次交换交换完成后再次扫描整个数组找到当前状态下的最小值索引做第二次交换。public static void swapMaxMinByTwoScans(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 第一遍扫描找最大值索引 int maxIdx 0; for (int i 1; i n; i) { if (arr[i] arr[maxIdx]) { maxIdx i; } } // 最大值与第一个元素交换 int temp arr[0]; arr[0] arr[maxIdx]; arr[maxIdx] temp; // 第二遍扫描在交换后的数组里重新找最小值索引 int minIdx 0; for (int i 1; i n; i) { if (arr[i] arr[minIdx]) { minIdx i; } } // 最小值与最后一个元素交换 temp arr[n - 1]; arr[n - 1] arr[minIdx]; arr[minIdx] temp; }这个方案的核心思路是把“状态同步”问题直接从源头消灭第二次扫描是在第一次交换完成后的新数组上进行的找出来的最小值索引天然就是最新的不需要任何补救逻辑。拿之前的{1, 2, 3, 4, 5}验证第一遍扫描找到最大值索引4交换0和4数组变成{5, 2, 3, 4, 1}第二遍扫描从新数组里找最小值发现最小值1已经滚到了索引4然后拿索引4和最后一个索引4自交换数组保持不变。最终输出{5, 2, 3, 4, 1}完全正确。代价是两次全数组遍历。时间复杂度仍然是O(n)常数系数翻倍。对十万、百万级别的数组来说这点额外开销其实毫不起眼但如果这是一个会被调用千万次的工具方法一次遍历显然更体面。2.2 方案二一次扫描交换后修正被挪走的索引一次扫描的同时记录最大值索引和最小值索引然后做交换交换后检测“最小值是否被波及”是这道题最经典的解法。public static void swapMaxMinByOneScan(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; int maxIdx 0; int minIdx 0; for (int i 1; i n; i) { if (arr[i] arr[maxIdx]) { maxIdx i; } if (arr[i] arr[minIdx]) { minIdx i; } } // 第一步最大值与第一个元素交换 int temp arr[0]; arr[0] arr[maxIdx]; arr[maxIdx] temp; // 如果最小值原本就在首元素它已经被第一次交换挪到了 maxIdx 位置 if (minIdx 0) { minIdx maxIdx; } // 第二步最小值与最后一个元素交换 temp arr[n - 1]; arr[n - 1] arr[minIdx]; arr[minIdx] temp; }关键就在第一次交换之后的那三行判断。为什么只需要判断minIdx 0因为第一次交换只会动两个位置索引0和索引maxIdx。如果最小值原本的索引不是0说明它不在被挪动的位置上索引依然有效如果最小值原本就在索引0那它必然被交换到了maxIdx这个位置更新minIdx指向maxIdx就能继续正常工作。再考虑一个连别人会忽略的角落如果maxIdx 0也就是最大值本来就在首元素第一次交换是自交换数组没变此时如果minIdx 0说明最大最小同时在首元素——这只有在所有元素相等时才会发生。更新minIdx为maxIdx仍然等于0后续自交换也不改变数组逻辑依然成立。拿{1, 2, 3, 4, 5}再验证一遍扫描得到maxIdx4、minIdx0交换0和4数组变成{5, 2, 3, 4, 1}此时minIdx0成立更新minIdx4最后拿索引4和最后一个索引4自交换数组保持不变。结果正确。2.3 方案三对称写法先交换最小值那边既然先做“最大换首元素”需要修正minIdx那自然有人想到先做“最小换尾元素”然后修正maxIdx不就好了逻辑完全对称。public static void swapMaxMinByMinFirst(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; int maxIdx 0; int minIdx 0; for (int i 1; i n; i) { if (arr[i] arr[maxIdx]) { maxIdx i; } if (arr[i] arr[minIdx]) { minIdx i; } } // 第一步最小值与最后一个元素交换 int temp arr[n - 1]; arr[n - 1] arr[minIdx]; arr[minIdx] temp; // 如果最大值原本就在尾元素它已经被挪到了 minIdx 位置 if (maxIdx n - 1) { maxIdx minIdx; } // 第二步最大值与第一个元素交换 temp arr[0]; arr[0] arr[maxIdx]; arr[maxIdx] temp; }这个方案在写法上和方案二互为镜像选哪个纯看个人习惯。我见过不少开发者觉得先做最小值的交换更顺手因为“先照顾尾部的需求”让他们有一种先把危险解除的安心感逻辑上两者其实等价。2.4 三种方案怎么选对比维度二次扫描方案一次扫描索引修正先交换最小值索引修正遍历次数两次一次一次逻辑理解难度最容易中等中等出错风险低中等需理解修正逻辑中等代码行数约20行约22行约22行适用场景教学、追求绝对稳妥对性能敏感的工具方法与方案二习惯偏好相关我的建议是如果你是在学习阶段第一次写这道题用二次扫描方案先把正确性放在第一位如果你是在优化已有代码或者面试现场展示功底一次扫描加修正的写法更能体现你对副作用的理解。3. 边界情况与测试用例把数组的极端形态都试一遍写数组题目最怕的不是逻辑复杂而是自以为逻辑正确、结果边界情况一个没测。下面这组测试用例覆盖了这道题的所有关键形态可以直接拿来用。3.1 完整测试用例矩阵用例编号输入数组期望输出解析1{5, 3, 8, 1, 9, 2}{9, 3, 8, 2, 5, 1}常规情况最大最小都不在端点2{1, 2, 3, 4, 5}{5, 2, 3, 4, 1}最大在尾、最小在首最容易翻车的用例3{9, 3, 8, 1, 5, 2}{9, 3, 8, 2, 5, 1}最大值已在首元素第一步自交换4{5, 3, 8, 2, 9, 1}{9, 3, 8, 2, 5, 1}最小值已在尾元素第二步自交换5{7, 7, 7, 7}{7, 7, 7, 7}所有元素相等最大最小索引重合6{3}{3}数组长度1不满足交换条件7{2, 1}{2, 1}最大在首、最小在尾两次都是自交换8{-5, 3, 8, -1, 9, 2}{9, 3, 8, -1, 2, -5}包含负数比较逻辑不受影响9{5, 9, 8, 1, 9, 0}{9, 5, 8, 1, 9, 0}存在重复最大值取第一次出现的最大元素10null或{}原样返回空输入防御第9个用例值得多说一句。数组里有两个9分别在索引1和索引4。题目只说“最大的与第一个元素交换”没有说明重复最大元素取哪个。最常见的约定是取第一次出现的也就是索引1的那个9如果要求取最后一个扫描时的比较条件就要改成。别看这只是个等号的区别真实需求里很可能就是个隐藏的坑。3.2 测试代码怎么组织写个带main方法的测试类是最直接的适合快速验证如果要长期维护建议用JUnit的ParameterizedTest做参数化测试。下面给一个main方法的版本方便直接复制运行public class ArraySwapDemo { public static void main(String[] args) { int[][] testCases { {5, 3, 8, 1, 9, 2}, {1, 2, 3, 4, 5}, {9, 3, 8, 1, 5, 2}, {5, 3, 8, 2, 9, 1}, {7, 7, 7, 7}, {3}, {2, 1}, {-5, 3, 8, -1, 9, 2}, {5, 9, 8, 1, 9, 0} }; for (int[] testCase : testCases) { int[] copy testCase.clone(); swapMaxMinByOneScan(copy); System.out.println(原始数组: java.util.Arrays.toString(testCase) - 交换后: java.util.Arrays.toString(copy)); } } // 这里放 swapMaxMinByOneScan 方法的实现 }注意测试时先clone()一份原数组不然打印“原始数组”时它已经被改掉了复盘会很痛苦。这个细节看着小实测时特别容易让人误判输出结果。3.3 实测输出和预期对不对得上把上面九个用例跑一遍正常实现的输出应该逐行对应3.1表格里的期望值。我建议你拿到代码后一定要亲手跑一次尤其是用例2和用例9这两个是最能检验实现是否踩中交换顺序坑的试金石。如果用例2输出成了{1, 2, 3, 4, 5}说明那些对索引的处理没生效如果用例9输出成了{9, 5, 8, 1, 9, 0}而不是把第二个9换到开头说明这不是你想要的行为需要检查比较条件里的是否需要改成。4. 典型错误写法复盘为什么你的代码一测就挂我把这些年实际见到的错误写法整理了一下基本就集中在四类对照自己的代码看看有没有中招。4.1 错误一两个交换都基于旧数组的索引先扫描拿到maxIdx和minIdx然后直接两次swap不做任何修正。这是最经典的错误也是题目本身埋的坑。它只在最大最小都不在端点的情况下正确一旦遇到类似{1, 2, 3, 4, 5}的输入就出问题而且这种输入在实际使用中一点都不罕见。解决办法就是把第一次交换后受影响的那一方索引修正掉或者干脆用二次扫描。4.2 错误二比较的是值而不是索引有些人会写出这样的逻辑先找出最大值和最小值本身然后再写循环找到它们在数组中的位置。比如先int maxVal Integer.MIN_VALUE;然后遍历找到maxVal再根据maxVal找下标。这在小数组上没问题但一旦有重复元素indexOf(maxVal)默认返回第一个匹配的位置如果题目隐含“取最后出现的最大元素”之类的需求就会出偏差。更根本的问题是白白多做了一次或者两次遍历代码还变长了。直接记录索引是更干净的做法。4.3 错误三交换时分不清自交换和普通交换有人可能会写一个通用的swap(arr, i, j)把第0个和第maxIdx个交换时没有意识到两者可能是同一个位置。自交换本身在逻辑上没错但如果你在swap方法里加了多余的状态判断或者记录了一次“交换日志”自交换带来的副作用就可能污染结果。至少要在注释里标明“这里可能是自交换属于正常情况”。4.4 错误四没有防御空数组和单元素数组当输入为null、长度为0或长度为1时程序里所有对arr[0]和arr[arr.length - 1]的访问都有崩溃或产生无意义结果的风险。真实项目调用方不会保证输入合法防御性编程是基本功。方法开头三行if (arr null || arr.length 2) { return; }把这句话养成习惯能挡掉一大批运行时异常。4.5 一个完整的排查思路示例我见过一个同学的代码长这样int maxIdx 0, minIdx 0; for (int i 1; i arr.length; i) { if (arr[i] arr[maxIdx]) maxIdx i; if (arr[i] arr[minIdx]) minIdx i; } swap(arr, 0, maxIdx); swap(arr, arr.length - 1, minIdx);他测{5, 3, 8, 1, 9, 2}通过了测{9, 3, 8, 1, 5, 2}通过了测{1, 2, 3, 4, 5}挂了。排查思路应该这样走先看第一次交换前数组状态再看第一次交换后数组状态对比minIdx在交换前后指向的元素到底变没变。一旦意识到“交换前找到的minIdx在交换后可能不是最小值了”问题的根源也就找到了——不是交换方法写错了而是索引状态没同步。这个排查思路值得记住因为它不只能修这道题。任何涉及“先读取状态、再修改状态、最后使用旧状态”的程序都可能出现同样的失效模式。5. 延伸思考这道题背后的几个编程习惯问题题目本身不难但它背后涉及的几个问题对新手来说价值比题目本身大得多。5.1 从“自交换”看边界处理习惯自交换并不算错误但它是个信号你的算法在某个边界条件下退化成了“什么都不做”。在交换操作有额外开销的系统中比如对象数组交换要拷贝引用可能还要触发其他逻辑提前判断if (i j) return;可以省掉无意义的操作。这道题里的自交换无伤大雅但养成“交换前判断是否同位置”的习惯到了写复杂排序算法时会很有用。5.2 从“重复元素”看需求确认“最大的元素”遇到重复值怎么办题目通常不说明但你写代码前必须自己把语义定下来取第一个还是取最后一个还是任意一个这在实际开发中对应的就是需求模糊地带。与其写完了再改不如动手前就问清楚或者在自己的文档里写明确认过的约定。这道题里比较条件用还是就是两种语义的直接体现。5.3 从“一次扫描还是两次扫描”看复杂度决策二次扫描方案常数因子是2一次扫描方案需要额外理解和维护一行修正逻辑。现实中你面对的很多选择都是这样的权衡更简单的代码 vs 更少的计算量。我的建议是除非你能证明性能是瓶颈否则优先选简单代码一旦选了一次扫描就必须保证修正逻辑旁边有清晰的注释不然三个月后的自己会对着这行代码发呆。5.4 进阶如果要求最大和第一个交换、第二大和第二个交换……呢这就是经典的选择排序思路。每一轮从未处理区间里挑出最大值和当前处理的起始位置交换然后起始位置前进一格继续下一轮。你会发现这道题的“一次交换”就是选择排序的“一轮迭代”去掉最小值那半部分。从单次交换扩展到多轮迭代是把基础题变成排序算法的最自然路径感兴趣的可以从这里入手复习一下选择排序的写法。5.5 进阶自定义对象数组怎么办如果数组元素不是int而是自定义对象比较逻辑就不能直接用和。Java里要么让对象实现ComparableT接口要么给扫描方法传入一个ComparatorT。交换本身不受影响变的只是比较部分。这也能看出把“找最值”和“交换”分成独立的关注点代码的复用性会好很多——找最值的逻辑关心的是比较规则交换的逻辑只关心位置。个人体会是这道题适合作为“写完代码后主动补测试用例”的训练素材。真正让我把“边界情况”刻进脑子里的不是哪个框架文档而是这种看着简单却能连续踩坑的小题目。要是你手头还有类似的数组操作题建议都拿这套方法论过一遍先列边界形态再写实现最后补测试。这套流程跑顺了比多刷十道题都管用。