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

从华东师大机试题E‘乘法’出发，手把手带你玩转‘多路归并’求第K大数

news 2026/4/21 15:18:38

从矩阵乘积到多路归并：第K大数问题的通用解法剖析

在算法竞赛和编程面试中，"Top K"问题是一类经典且高频出现的题型。这类问题不仅考察选手对基础数据结构的掌握程度，更能检验其将数学思维转化为高效算法的能力。本文将以华东师范大学计算机考研复试机试题中的"矩阵乘积第K大数"问题为切入点，系统性地剖析多路归并算法在这一类问题中的应用框架。

1. 问题定义与暴力解法

给定两个数组A和B，长度分别为n和m。我们定义矩阵C，其中每个元素C[i][j] = A[i] × B[j]。现在需要找出这个矩阵中第K大的数值。

最直观的暴力解法是生成所有n×m个乘积，然后进行排序：

def kth_largest_product_naive(A, B, K): products = [] for a in A: for b in B: products.append(a * b) products.sort(reverse=True) return products[K-1]

这种方法的时间复杂度为O(nm log(nm))，当n和m达到10^5量级时，显然无法在合理时间内完成计算。这迫使我们寻找更高效的算法。

2. 多路归并的核心思想

多路归并算法(Multiway Merge)是解决Top K问题的利器，其核心在于避免生成全部解空间，而是通过优先级队列逐步"探索"可能的最优解。

对于当前问题，我们可以将矩阵C视为n个有序序列的集合：

序列1：A[1]×B[1], A[1]×B[2], A[1]×B[3], ...
序列2：A[2]×B[1], A[2]×B[2], A[2]×B[3], ...
...
序列n：A[n]×B[1], A[n]×B[2], A[n]×B[3], ...

假设数组A和B都已按降序排列，那么每个序列也是降序排列的。此时，整个矩阵的最大值必然是A[1]×B[1]。

关键观察：当已知第i大的元素来自某个位置(A[x]×B[y])时，第i+1大的元素只可能是以下两种情况之一：

A[x+1]×B[y]
A[x]×B[y+1]

这个性质构成了多路归并算法的基础。

3. 算法实现与优化

基于上述观察，我们可以使用最大堆来维护候选元素：

import heapq def kth_largest_product(A, B, K): A.sort(reverse=True) B.sort(reverse=True) heap = [] visited = set() heapq.heappush(heap, (-A[0]*B[0], 0, 0)) visited.add((0, 0)) for _ in range(K-1): current = heapq.heappop(heap) i, j = current[1], current[2] if i+1 < len(A) and (i+1, j) not in visited: heapq.heappush(heap, (-A[i+1]*B[j], i+1, j)) visited.add((i+1, j)) if j+1 < len(B) and (i, j+1) not in visited: heapq.heappush(heap, (-A[i]*B[j+1], i, j+1)) visited.add((i, j+1)) return -heap[0][0]

算法复杂度分析：

排序两个数组：O(n log n + m log m)
堆操作：每次插入和删除操作O(log K)，进行K次
总复杂度：O(n log n + m log m + K log K)

当K远小于n×m时，这种方法的效率显著高于暴力解法。

4. 同类问题横向对比

多路归并算法可以解决多种形式的Top K问题，下面列举几个典型例子：

问题类型	示例题目	关键特征
多数组归并	合并K个有序链表	每个序列本身有序
数学乘积	丑数II	数字由质因数乘积构成
矩阵搜索	有序矩阵第K小元素	行列分别有序
路径问题	最短路中的第K短路径	状态转移产生新候选

以力扣378题"有序矩阵中第K小的元素"为例，其解法与本文讨论的问题高度相似：

def kthSmallest(matrix, k): n = len(matrix) heap = [] for i in range(n): heapq.heappush(heap, (matrix[i][0], i, 0)) for _ in range(k-1): val, i, j = heapq.heappop(heap) if j+1 < n: heapq.heappush(heap, (matrix[i][j+1], i, j+1)) return heap[0][0]

5. 算法模板与扩展应用

基于以上分析，我们可以抽象出一个通用的多路归并算法模板：

初始化阶段：
- 对输入数据进行必要的预处理（如排序）
- 将各路的第一个候选元素加入优先队列
- 建立访问记录以避免重复
迭代阶段：
- 进行K-1次取出当前最大值/最小值的操作
- 每次取出后，生成新的候选元素加入队列
- 确保不重复访问已处理的位置
结果获取：
- 第K次访问堆顶元素即为所求

对于更复杂的问题，如"找出两个数组乘积的第K小和"，我们可以通过调整排序方向和堆的性质来适配：

def kth_smallest_product(A, B, K): A.sort() B.sort() heap = [] visited = set() heapq.heappush(heap, (A[0]*B[0], 0, 0)) visited.add((0, 0)) for _ in range(K-1): current = heapq.heappop(heap) i, j = current[1], current[2] if i+1 < len(A) and (i+1, j) not in visited: heapq.heappush(heap, (A[i+1]*B[j], i+1, j)) visited.add((i+1, j)) if j+1 < len(B) and (i, j+1) not in visited: heapq.heappush(heap, (A[i]*B[j+1], i, j+1)) visited.add((i, j+1)) return heap[0][0]