当前位置：首页 > news >正文

Java数组去极值算法：从面试题到工程实践的边界处理与性能优化

news 2026/8/3 12:02:50

1. 从一道经典面试题说起：评委打分的“去极值”算法

最近在带新人，顺手翻出了几道经典的Java基础题给他们练手，其中一道就是“评委打分，去掉一个最高分和一个最低分，然后计算平均分”。这题目乍一看简单得不行，不就是数组操作加个算术平均嘛。但当我让他们现场手写时，问题就暴露出来了：有人用Arrays.sort()排序后掐头去尾，有人写了两层循环找最大最小值，还有人直接上手Stream API但没处理好边界。更关键的是，几乎没人第一时间去考虑“如果所有分数都一样怎么办？”或者“如果评委人数少于3个，这规则还适用吗？”这类边界情况。

这道题之所以能成为面试常客，甚至出现在一些初级工程师的笔试题里，正是因为它麻雀虽小，五脏俱全。它考察的远不止是语法，而是对数组基础操作、逻辑严谨性、边界条件处理以及算法效率的直观理解。一个合格的实现，应该像瑞士军刀一样，简洁、可靠、能应对各种情况。今天，我就结合自己这些年面试别人和被面试的经验，把这个看似简单的功能掰开揉碎了讲，聊聊不同实现方案背后的考量，以及在实际业务代码里，我们可能会怎么处理类似的需求。

2. 需求拆解与核心逻辑建模

在动手写代码之前，我们得先把需求彻底搞清楚。题目描述是“去除最高分和最低分，然后获取平均值”，但这短短一句话里藏着好几个需要明确的点。

2.1 明确输入与输出

首先，输入是什么？通常，我们会有一个包含所有评委打分的数组，比如double[] scores或者int[] scores。使用double是为了能处理带小数的分数，更通用。输出则是一个代表平均值的浮点数。

2.2 “去除”的精确含义

这里的“去除”是指从计算样本中排除。假设有N个分数，去除一个最高分和一个最低分后，参与求平均的分数个数就是 N-2。因此，平均值的计算公式是：(总分 - 最高分 - 最低分) / (N - 2)。这里就引出了第一个边界条件：N必须大于2。如果只有1个或2个评委，去掉最高最低分后就没分数可用了，这种业务场景下通常需要抛出异常或返回一个特殊值（如0或原分数），具体取决于业务规则。

2.3 处理并列的极值

这是一个极易忽略的坑。如果最高分有多个相同的（比如两个评委都打了10分），或者最低分有多个相同的，我们“去除”几个？按照常见的业务理解（尤其是体育比赛、歌唱比赛规则），通常是只去掉一个最高分和一个最低分，即使有并列。也就是说，如果有两个最高分都是10分，我们只去掉其中一个，另一个10分依然参与计算。我们的算法必须准确体现这一点，而不是把所有等于极值的分数都去掉。

2.4 算法目标

基于以上分析，我们的算法需要：

遍历一次数组，准确找出唯一的一个最大值和唯一的一个最小值（即使有并列，也只记录第一次找到的索引或值）。
计算数组中所有元素的总和。
根据公式(总和 - 最大值 - 最小值) / (数组长度 - 2)计算结果。
妥善处理数组长度小于等于2的边界情况。

3. 基础实现方案：一次遍历的“侦察兵”法

最直接也最高效的方法，是在一次遍历中同时完成求和、找最大值、找最小值这三项任务。我把它叫做“侦察兵”法：想象你带着一队侦察兵（循环）探查整个数组地形，同时记录下当前遇到的海拔最高点（最大值）、海拔最低点（最小值）以及总路程（总和）。

public static double calculateAverageExcludingExtremes(double[] scores) { if (scores == null || scores.length <= 2) { // 边界处理：返回0或抛出异常，依业务而定 // throw new IllegalArgumentException("评委人数必须大于2"); return 0.0; } double sum = 0; double max = scores[0]; double min = scores[0]; for (double score : scores) { sum += score; if (score > max) { max = score; } if (score < min) { min = score; } } double adjustedSum = sum - max - min; return adjustedSum / (scores.length - 2); }

为什么这是最优解？它的时间复杂度是 O(n)，只需要遍历数组一次，空间复杂度是 O(1)，只用了几个临时变量。对于任何规模的数据，这都是效率最高的做法。在面试中，能写出这个版本，说明你对循环和基本算法思想掌握得很扎实。

这里有三个关键的实操细节：

初始化：max和min不能初始化为0，而必须初始化为数组的第一个元素scores[0]。这是因为如果数组里全是负数，初始化为0的max就永远不会被更新，导致结果错误。
并列极值处理：这段代码中，当遇到等于当前max或min的分数时，if条件不成立，极值不会被更新。这正好符合我们“只去掉一个”的需求。第一次找到的极值被记录，后续相同的值被视为普通分数。
精度问题：使用double计算总和与平均值可能存在浮点数精度误差。对于金融或高精度评分场景，可以考虑使用BigDecimal。但在大多数表演评分场景下，double的精度足够。

4. 排序方案的误区与局限性

很多新手的第一反应是排序。先调用Arrays.sort(scores)，然后去掉头尾元素，再对中间部分求平均。

// 不推荐的排序方案 public static double calculateAverageBySorting(double[] scores) { if (scores == null || scores.length <= 2) { return 0.0; } Arrays.sort(scores); double sum = 0; // 从索引1开始，到倒数第二个结束 for (int i = 1; i < scores.length - 1; i++) { sum += scores[i]; } return sum / (scores.length - 2); }

这个方法看起来清晰，但为什么它通常不是最佳答案呢？

4.1 效率损失Arrays.sort()对于对象数组使用 TimSort，对于基本类型数组使用双轴快速排序，其平均时间复杂度是 O(n log n)。这比我们一次遍历的 O(n) 要慢。当评委数量很多（比如成千上万个线上用户评分）时，这个差异会变得明显。

4.2 破坏了原始数据排序是原地操作，它会改变传入数组的顺序。如果调用方后续还需要原始的分数序列做其他分析（比如分析打分分布），这个副作用就是致命的。当然，你可以先拷贝数组再排序，但这又增加了 O(n) 的空间和时间开销。

4.3 并列极值处理可能出错排序后，所有相同的最高分会紧挨着出现在末尾。如果我们简单地“去掉头尾”，实际上是把所有等于极值的分数都排除了。例如分数为[7, 9, 9, 8, 9]，排序后是[7,8,9,9,9]。去掉头尾后剩下[8,9,9]，总和是26，平均是8.67。而用“侦察兵”法，最大值是第一个9，最小值是7，总和42，减去后是26，平均同样是8.67。在这个例子里结果巧合相同。但如果分数是[9, 6, 9, 9]，排序去头尾法会错误地去掉两个9，导致计算错误。

注意：在面试中，如果你提出排序方案，面试官很可能会追问时间和空间复杂度，以及是否修改原数组。你必须能清楚地分析出这些优缺点。

5. 使用Stream API的现代写法

对于使用Java 8及以上版本的开发者，Stream API提供了一种声明式的、函数式的解决方案。

import java.util.Arrays; import java.util.DoubleSummaryStatistics; public static double calculateAverageUsingStream(double[] scores) { if (scores == null || scores.length <= 2) { return 0.0; } DoubleSummaryStatistics stats = Arrays.stream(scores).summaryStatistics(); double sum = stats.getSum(); double max = stats.getMax(); double min = stats.getMin(); // 问题：如何确保只减去一个max和一个min？ // 直接 sum - max - min 会错误地减去所有极值吗？ // 需要找到第一个最大和第一个最小的索引 }

Stream方案的陷阱看起来很美，但有个大问题：DoubleSummaryStatistics提供的getMax()和getMin()是值，而不是索引。我们无法知道最大值和最小值在数组中出现了几次，以及第一次出现的位置。直接用sum - max - min会犯和排序法类似的错误：如果极值有重复，就多减了。因此，一个完整的Stream实现反而更复杂，需要结合索引来操作：

public static double calculateAverageUsingStreamCorrectly(double[] scores) { if (scores == null || scores.length <= 2) { return 0.0; } // 找到第一个最大值和最小值的索引 double maxValue = Arrays.stream(scores).max().orElse(Double.NaN); double minValue = Arrays.stream(scores).min().orElse(Double.NaN); int maxIndex = IntStream.range(0, scores.length) .filter(i -> scores[i] == maxValue) .findFirst() .orElse(-1); int minIndex = IntStream.range(0, scores.length) .filter(i -> scores[i] == minValue) .findFirst() .orElse(-1); double sum = Arrays.stream(scores).sum(); // 确保不是同一个索引（虽然概率极低） if (maxIndex == minIndex) { // 如果最大值和最小值是同一个数（即所有分数相同），则任意去掉一个即可 sum -= maxValue; return sum / (scores.length - 1); // 这里变成了去掉一个分数 } double adjustedSum = sum - maxValue - minValue; return adjustedSum / (scores.length - 2); }

这个实现虽然功能正确，但为了找索引遍历了多次数组（找最大值、找最小值、找最大值索引、找最小值索引、求和），效率远低于一次遍历的基础方法。它展示了Stream的灵活性，但在性能敏感的场合并不适用。

6. 边界条件与异常处理的实战经验

在真实项目中，代码的健壮性比算法炫技更重要。下面我们来详细处理各种边界情况。

6.1 输入为空或长度不足

这是最基本的防御性编程。方法开头必须检查。

public static double calculateAverageRobust(double[] scores) throws IllegalArgumentException { // 1. 空指针检查 if (scores == null) { throw new IllegalArgumentException("评分数组不能为null"); } // 2. 长度检查 int len = scores.length; if (len <= 2) { // 业务决策点：是抛出异常，还是返回一个默认值？ // 决策依据：调用方是否认为这是错误情况。 // 方案A：抛出异常，强制调用方处理 throw new IllegalArgumentException("评委人数必须大于2，当前人数：" + len); // 方案B：返回特殊值（如0或所有分数的平均） // if (len == 0) return 0.0; // if (len == 1) return scores[0]; // if (len == 2) return (scores[0] + scores[1]) / 2.0; } // ... 后续计算逻辑 }

6.2 所有分数相同的情况

当所有分数都相等时，最大值等于最小值。根据我们的公式总和 - max - min，就变成了总和 - 2 * score。这符合逻辑吗？符合。因为我们要去掉一个最高分和一个最低分，而它们恰好是同一个值，所以总和里需要减去两份这个值。最终平均值等于(n*score - 2*score) / (n-2) = score。结果是合理的，所有分数相同，去掉两个一样的，剩下的还是这个分数，平均分不变。我们的“侦察兵”法能正确处理这种情况。

6.3 浮点数的精度与比较

在找最大值和最小值时，我们使用了>和<进行比较。对于浮点数，直接使用==判断相等是不可靠的，因为存在精度误差。但在本算法中，我们只使用>和<，不直接判断相等，因此避免了浮点数等值比较的经典陷阱。然而，如果业务上需要判断“是否已经去掉极值”，或者处理非常接近的分数，就需要考虑引入一个误差容忍度（epsilon）。

// 如果需要处理浮点数精度，比较时可以这样写 private static final double EPSILON = 1e-10; if (Math.abs(score - max) < EPSILON) { // 视为相等，根据业务决定是否更新max（通常不更新） }

6.4 分数为负数或超出合理范围

如果评分标准是0-10分，但数组里出现了-1或100，逻辑上我们的算法依然能工作，但结果可能没有业务意义。这属于数据校验的范畴，应该在数据进入系统时就做好约束，而不是在计算平均值的函数里处理。不过，为了健壮性，可以添加一个可选的校验：

public static double calculateAverageWithValidation(double[] scores, double minValid, double maxValid) { // ... 空值和长度检查 for (double score : scores) { if (score < minValid || score > maxValid) { throw new IllegalArgumentException(String.format("分数 %.2f 超出有效范围 [%.2f, %.2f]", score, minValid, maxValid)); } } // ... 后续计算 }

7. 性能对比与单元测试验证

光说不练假把式，我们写个简单的测试来验证不同方法的正确性和性能。

7.1 单元测试用例设计

一个好的测试应该覆盖正常情况和所有边界情况。

import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.*; class JudgeScoreCalculatorTest { @Test void testNormalCase() { double[] scores = {9.1, 8.5, 9.8, 8.9, 9.3}; double expected = (9.1 + 8.5 + 8.9 + 9.3) / 4.0; // 去掉9.8和8.5 assertEquals(expected, calculateAverageExcludingExtremes(scores), 1e-10); } @Test void testAllScoresSame() { double[] scores = {7.5, 7.5, 7.5, 7.5}; assertEquals(7.5, calculateAverageExcludingExtremes(scores), 1e-10); } @Test void testDuplicateMaxAndMin() { // 两个最高分，一个最低分 double[] scores = {5.0, 10.0, 9.0, 10.0, 8.0}; // 去掉一个10.0和一个5.0，剩下 [10.0, 9.0, 8.0]，平均9.0 assertEquals(9.0, calculateAverageExcludingExtremes(scores), 1e-10); } @Test void testOnlyThreeScores() { double[] scores = {10.0, 5.0, 8.0}; // 去掉10.0和5.0，剩下8.0，平均8.0 assertEquals(8.0, calculateAverageExcludingExtremes(scores), 1e-10); } @Test void testInvalidInput() { // 测试长度不足 double[] twoScores = {9.0, 8.0}; assertThrows(IllegalArgumentException.class, () -> calculateAverageExcludingExtremes(twoScores)); // 测试null assertThrows(IllegalArgumentException.class, () -> calculateAverageExcludingExtremes(null)); } }

7.2 简单性能对比

我们可以写一个简单的性能测试，感受一下不同数据规模下的差异。

public class PerformanceComparison { public static void main(String[] args) { int size = 1000000; // 100万个评分 double[] scores = new double[size]; Random rand = new Random(); for (int i = 0; i < size; i++) { scores[i] = rand.nextDouble() * 10; // 生成0-10之间的随机分数 } // 预热 calculateAverageExcludingExtremes(Arrays.copyOf(scores, 100)); // 测试一次遍历法 long startTime = System.nanoTime(); double result1 = calculateAverageExcludingExtremes(scores); long endTime = System.nanoTime(); System.out.printf("一次遍历法: 结果=%.4f, 耗时=%.2f ms%n", result1, (endTime - startTime) / 1_000_000.0); // 测试排序法（需要拷贝数组，因为排序会修改原数组） startTime = System.nanoTime(); double[] copy = Arrays.copyOf(scores, scores.length); double result2 = calculateAverageBySorting(copy); endTime = System.nanoTime(); System.out.printf("排序法: 结果=%.4f, 耗时=%.2f ms%n", result2, (endTime - startTime) / 1_000_000.0); } }

在我的笔记本上运行，一次遍历法通常比排序法快一个数量级。当数据量达到百万级时，这个差异会从毫秒级扩大到几十甚至上百毫秒。在追求高性能的服务中，这个优化是有意义的。

8. 业务场景扩展：不只是去掉一个

现实中的评分规则可能更复杂。比如“去掉两个最高分和两个最低分”，或者“去掉最高最低的10%”。这时，我们的算法需要如何调整？

8.1 去掉多个最高分和最低分

假设要去掉t个最高分和t个最低分。最直观的方法是排序，然后取中间的部分。这在t较小且数组不大时是可以接受的。

public static double calculateAverageExcludingMultiple(double[] scores, int t) { if (scores == null || scores.length <= 2 * t) { throw new IllegalArgumentException("去掉的分数数量过多"); } Arrays.sort(scores); double sum = 0; for (int i = t; i < scores.length - t; i++) { sum += scores[i]; } return sum / (scores.length - 2 * t); }

8.2 使用优先队列（堆）处理海量数据

如果数据量极大（比如来自千万用户的实时评分流），而t值相对较小（比如只去掉前10名和后10名），排序整个数组就太浪费了。我们可以使用两个优先队列（堆）来高效地找出最大的t个元素和最小的t个元素。

用一个最小堆来保存最大的t个数。堆顶是这个集合里最小的数，也就是第t大的数。
用一个最大堆来保存最小的t个数。堆顶是这个集合里最大的数，也就是第t小的数。
遍历数组，维护这两个堆。
最后，总和减去两个堆中所有元素的和，再除以(n - 2t)。

这种方法的时间复杂度是 O(n log t)，当t << n时，比 O(n log n) 的排序要快得多。空间复杂度是 O(t)。这是典型的“用空间换时间”，也是处理大数据流Top K问题的标准思路。

8.3 加权平均与中位数

在一些严肃的评审中，可能还会用到加权平均（不同评委权重不同）或者直接使用中位数来避免极端值的影响。中位数的计算同样可以通过快速选择算法在平均O(n)时间内完成，这比排序求中位数更优。这些扩展都体现了同一个思想：根据具体的、变化的业务需求，选择最合适的算法和数据结构，而不是固守一个“标准答案”。

9. 从这道题看编程思维的培养

回过头看，“评委打分”这道题的价值，远远超出了它本身的代码行数。它像一块试金石，能快速检验出一个程序员的基本功和思维习惯。

9.1 思维误区：过度设计

新手容易犯的错误是“杀鸡用牛刀”。一看到数组和统计，就想用Stream；一听到排序，就想写个冒泡排序展示算法知识。但在生产环境中，简单、清晰、高效的代码才是最好的。一次遍历的“侦察兵”法，就是KISS原则（Keep It Simple, Stupid）的完美体现。在面试中，先给出这个最朴素的解法，并清晰阐述其时间和空间复杂度，往往比炫技更能赢得好感。

9.2 沟通的重要性

在动手写代码前，一定要和需求方（或面试官）确认细节。比如：