别光看答案！用2022蓝桥杯‘最少刷题数’题带你吃透中位数在算法竞赛中的应用

中位数在算法竞赛中的高阶应用：从蓝桥杯"最少刷题数"题解到实战进阶

算法竞赛中，中位数这一统计学概念常被忽视其潜在威力。2022年蓝桥杯Java B组的"最少刷题数"问题，恰恰揭示了中位数在解决"平衡类"问题中的独特价值。本文将带您深入剖析这道经典赛题，并拓展中位数在各类算法场景中的高阶应用技巧。

1. 问题本质与中位数思想的浮现

"最少刷题数"问题的核心要求是：为每个学生确定需要增加的刷题量，使得全班刷题数多于该学生的人数不超过少于他的人数。这本质上是一个数据分布平衡问题。

1.1 原始问题分析

给定学生刷题数组[12, 10, 15, 20, 6]，排序后得到[6, 10, 12, 15, 20]。观察发现：

• 当学生当前刷题数 ≥ 中位数12时，无需额外刷题（输出0）
• 当刷题数 < 12时，需要补足到中位数+1（即13题）

// 关键判断逻辑 if (nums[i] < middle) { System.out.print(middle - nums[i] + 1); } else { System.out.print(0); }

1.2 中位数的平衡特性

中位数之所以能解决此类问题，源于其两个核心性质：

1. 数量均分：将数据集分为数量相等的两部分
2. 距离最小化：与所有数据点的绝对差之和最小

数学表达为： 对于有序数组A，中位数m满足：

argmin ∑|A[i] - x| 的解 x = m

2. 算法实现的三重境界

2.1 基础解法：排序取中

最直接的实现方式是先排序后取中位数：

Arrays.sort(count); int index = (n % 2 == 0) ? n/2 : n/2 - 1; int middle = count[index];

时间复杂度：O(nlogn)
空间复杂度：O(n)

2.2 进阶优化：快速选择算法

当数据量极大时（如n>1e6），可以使用基于快速排序思想的快速选择算法：

public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length-1, nums.length-k); } private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) return nums[left]; int pivotIndex = partition(nums, left, right); if (k == pivotIndex) return nums[k]; else if (k < pivotIndex) return quickSelect(nums, left, pivotIndex-1, k); else return quickSelect(nums, pivotIndex+1, right, k); }

平均时间复杂度：O(n)
最坏情况：O(n²)（可通过随机化pivot避免）

2.3 终极方案：双堆动态维护

对于需要持续处理数据流的场景，可以建立两个堆：

// 大顶堆存储较小一半数字 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 小顶堆存储较大一半数字 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (maxHeap.size() < minHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { return maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2.0; }

插入复杂度：O(logn)
查询复杂度：O(1)

3. 中位数的变式应用场景

3.1 加权中位数问题

当每个数据点带有权重时，常规中位数不再适用。例如：

学生刷题数：[10,20,30] 对应权重： [3, 2, 1]（表示该成绩学生人数）

解决方案是计算累积权重中位数：

def weighted_median(data, weights): combined = sorted(zip(data, weights)) cumsum = 0 total = sum(weights) for value, weight in combined: cumsum += weight if cumsum >= total/2: return value

3.2 二维中位数寻址

在矩阵问题中，曼哈顿距离的最小化点即为各维度的中位数：

// 给定点集求最佳会面点（使总移动距离最小） public int minTotalDistance(int[][] grid) { List<Integer> rows = new ArrayList<>(); List<Integer> cols = new ArrayList<>(); for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { rows.add(i); cols.add(j); } } } Collections.sort(cols); int row = rows.get(rows.size()/2); // 行中位数 int col = cols.get(cols.size()/2); // 列中位数 return row + col; }

3.3 滑动窗口中位数

LeetCode 480题要求维护滑动窗口的中位数，解决方案：

from bisect import insort class Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: window = sorted(nums[:k]) medians = [] for i in range(k, len(nums)): medians.append((window[k//2] + window[(k-1)//2]) / 2) # 移除离开窗口的元素 window.pop(bisect.bisect_left(window, nums[i-k])) # 插入新元素 insort(window, nums[i]) medians.append((window[k//2] + window[(k-1)//2]) / 2) return medians

4. 实战训练与思维拓展

4.1 变形题训练

题目1（改变比较规则）： 给定学生刷题数组和每个学生的能力值，要求刷题数不少于他的学生中，能力值较低者不超过能力值较高者。

解决方案：

// 按能力值排序后，对刷题数做双重校验 Arrays.sort(students, (a,b)->a.ability-b.ability); int[] sortedProblems = new int[n]; // ...（处理逻辑类似但需交叉验证）

题目2（动态数据流）： 设计数据结构，支持：

1. addStudent(刷题数)
2. queryMinProblems(id)

解决方案：

class DynamicMedianTracker: def __init__(self): self.max_heap = [] # 较小一半 self.min_heap = [] # 较大一半 def addNum(self, num): heapq.heappush(self.max_heap, -num) heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) if len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def findMedian(self): if len(self.max_heap) > len(self.min_heap): return -self.max_heap[0] return (-self.max_heap[0] + self.min_heap[0]) / 2

4.2 性能对比实验

对不同规模数据测试各算法表现：

注意：双堆法在动态数据场景下优势明显，静态数据更适合快速选择

5. 系统设计与工程实践

5.1 分布式中位数计算

对于超大规模数据（如TB级），可采用T-digest算法：

// 使用T-digest库计算近似中位数 TDigest digest = TDigest.createAvlTreeDigest(100); for (double x : data) { digest.add(x); } double median = digest.quantile(0.5);

核心优势：

• 误差可控（通常<1%）
• 内存占用仅O(log n)
• 支持分布式合并

5.2 实时游戏排名系统

典型应用场景：每局游戏结束后快速确定玩家百分位：

class RankingSystem: def __init__(self): self.scores = [] self.counter = Counter() def addScore(self, playerId: int, score: int) -> None: bisect.insort(self.scores, score) self.counter[playerId] = score def getPercentile(self, playerId: int) -> int: score = self.counter[playerId] pos = bisect.bisect_left(self.scores, score) return (pos * 100) // len(self.scores)

6. 数学本质与算法选择

理解中位数问题的数学本质，能帮助我们在面对新问题时快速识别模式：

1. L1范数最小化：中位数是使绝对偏差和最小的点
2. 分治思想：快速选择算法体现了减治策略
3. 流式计算：双堆法展示了如何用有限内存处理无限数据

当遇到以下特征的问题时，考虑中位数解法：

• 需要找到"中心点"或"平衡点"
• 目标是最小化绝对差而非平方差
• 数据分布不均匀或有离群点时

// 典型问题判断流程 if (problemRequires("balance") || optimizationTarget("min absolute difference")) { considerMedianSolution(); }