TikTok 矩阵第 k 小：先确认排序保证再选算法

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 描述未说明矩阵是否行列排序；代码采用任意整数行、可不等长的通用合同。
• k从1，重复项各算一位，总元素不足k拒绝。

解题路线

1. 扫描所有元素，最大堆维护截至当前最小 k 项。未满先入堆，满后仅比堆顶更小的项替换；堆顶始终是目前第 k 小。
2. 扫描结束堆有 k 项才能返回。该法不依赖二维邻接或排序，因此没有编造条件。
3. 若每行有序，可对每行首项建最小堆，弹 k 次并推进该行；若行列有序，可值域二分配线性计数，但要证明计数和离散值边界。
4. k 接近元素总数时，维护较大的另一端或排序也可能更合适；算法选择依据内存、访问方式和规模。

手动走一遍

[[9,1],[3,1,7]] 第3小为3，两个1分别占前两位。有序[[1,3],[2,4]]虽然也可堆扫描，但不能从一张有序样例推断所有输入有序。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

import heapq


def matrix_kth_smallest(rows, k):
    """No sortedness assumed; duplicates count separately, ragged rows allowed."""
    count, heap = 0, []
    if k < 1:
        raise ValueError('positive one-based rank required')
    for row in rows:
        for value in row:
            count += 1
            if len(heap) < k:
                heapq.heappush(heap, -value)
            elif value < -heap[0]:
                heapq.heapreplace(heap, -value)
    if count < k:
        raise ValueError('rank exceeds element count')
    return -heap[0]

复杂度

N元素，O(N log(k+1)) 时间、O(k) 工作空间；通用扫描至少读全部元素。行排序优化 O(rows+k log rows) 需确认条件。

易错点与追问

容易失分的边界

• 未经确认套有序矩阵二分。
• 把重复值去重。
• k越界返回堆顶假装有效。

继续深挖

• 只按行排序如何合并？
• 有序矩阵如何线性计算≤mid的项数？