LeetCode 378. 有序矩阵中第 K 小的元素

约 6 分钟
文章信息 13 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 未掌握 20-50 字节跳动 快手 腾讯 滴滴 拼多多 亚马逊 虾皮
标签
数组 排序 二分查找 矩阵 堆（优先队列） Top N 问题 大顶堆
目录

题目描述

✅ 378. 有序矩阵中第 K 小的元素

image-20250528225537083

题意分析

给定一个 $n \times n$ 的矩阵，每一行从左到右递增，每一列从上到下递增，要返回把全部 $n^2$ 个元素按大小排好之后排在第 $k$ 位的那个数值。

要交付的是「值」而不是「坐标」，这一点决定了答案的形态：即使矩阵里有多个位置存着同一个数，只要它排名落在第 $k$ 位，返回那个数就算对。题目也明确说的是排序后的第 $k$ 个元素，不是第 $k$ 个不同的元素，所以重复值要占用各自的名次。

约束里有两个很强的信号。第一，只保证「行内有序」和「列内有序」，没有任何跨行跨列的保证，比如 [[1,3],[2,4]] 里第二行的开头 2 就比第一行的末尾 3 小，所以整个矩阵按行拼起来并不是一个有序序列。第二，$1 \le k \le n^2$，$k$ 一定合法，不需要处理越界。矩阵元素可以是负数，值域跨度可能很大。

边界情形：$n = 1$ 时矩阵只有一个元素，$k$ 只能是 1；$k = 1$ 时答案是左上角，$k = n^2$ 时答案是右下角；整个矩阵所有元素相同时，任何 $k$ 的答案都是那个值。

解法：值域二分 + 阶梯计数

核心思路

不必真的排出全部 $n^2$ 个元素。对候选值 $x$ 定义 count(x) 为矩阵中小于等于 $x$ 的元素个数，它随 $x$ 单调不减；第 $k$ 小的数就是最小的使 count(x) >= k 成立的值，因此可以在 [matrix[0][0], matrix[n-1][n-1]] 上做左边界二分。

count(x) 可用矩阵的行列有序性在 $O(n)$ 内求出：从左下角出发，若当前值不大于 $x$，同列上方 row + 1 个数都符合，计数后右移；否则当前行从该位置往右都过大，直接上移。行、列指针都只单向移动。

二分过程中始终保证答案在闭区间 [left, right] 内。若 count(mid) >= k，mid 可能就是第一个可行值，保留它并令 right = mid；否则 mid 及其左侧都不可行，令 left = mid + 1。区间收敛时得到最小可行值。若该值不在矩阵中，减一后的计数不会变化，便与“最小可行”矛盾，所以返回值一定是矩阵元素。

解题步骤

  1. 初始化值域 left = matrix[0][0]、right = matrix[n-1][n-1]。
  2. 取 mid = left + (right - left) / 2，从左下角阶梯扫描，统计 count(mid)。
  3. 若计数不少于 k，收缩右边界到 mid；否则令左边界为 mid + 1。
  4. 当 left == right 时返回该值。

例如 [[1,5,9],[10,11,13],[12,13,15]]、k = 8：count(8)=2、count(12)=6，左边界推进到 13；count(14)=8、count(13)=8，右边界收缩到 13，答案为 13。两个 13 会各占一个名次，无需去重。

代码实现

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countLessOrEqual(matrix, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private int countLessOrEqual(int[][] matrix, int target) {
        int n = matrix.length;
        int row = n - 1;
        int col = 0;
        int count = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    left := matrix[0][0]
    right := matrix[n-1][n-1]

    for left < right {
        mid := left + (right-left)/2
        if countLessOrEqual(matrix, mid) >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func countLessOrEqual(matrix [][]int, target int) int {
    n := len(matrix)
    row := n - 1
    col := 0
    count := 0
    for row >= 0 && col < n {
        if matrix[row][col] <= target {
            count += row + 1
            col++
        } else {
            row--
        }
    }
    return count
}

复杂度分析

  • 时间复杂度：$O(n \log(V+1))$，其中 $V=matrix[n-1][n-1]-matrix[0][0]$。值域二分进行 $O(\log(V+1))$ 轮，每轮阶梯计数耗时 $O(n)$。
  • 空间复杂度：$O(1)$，只使用常数个变量。

关键点总结

  • 二分的不是矩阵下标，而是答案的数值范围；判定条件是 count(x) >= k。
  • 左下角同时具有“本行最小、本列最大”的方向性，一次比较能排除一行或统计一列。
  • 这是“寻找第一个满足条件的值”，所以可行时保留 mid：right = mid。
  • 面试时要能说明返回值为何一定存在于矩阵中，以及重复值为何要重复计数。

易错点总结

  • 把矩阵按行展开后当作整体有序：[[1,3],[2,4]] 的第 2 小是 2，不是展开后的第 2 项 3。
  • 判定写成 count > k：第 $k$ 小要求至少有 k 个数不大于候选值，等号必须算可行。
  • 可行时写 right = mid - 1，或不可行时写 left = mid：前者可能排除答案，后者在相邻区间会死循环。
  • 阶梯方向写反：当前值 <= target 应统计同列上方并右移，过大才上移。
  • 对重复值去重：[[1,2],[1,3]]、k=2 的答案仍是 1，因为两个 1 各占一个名次。

相似题目

题目 难度 考察点
373. 查找和最小的 K 对数字 中等 两数组配对，用小顶堆按「下一个候选」逐个弹出前 $k$ 对
786. 第 K 个最小的质数分数 中等 二分的是浮点分数值，计数时统计不超过该比值的分数对
668. 乘法表中第k小的数 困难 矩阵不显式存在，每行的计数由 min(mid/i, n) 直接算出
719. 找出第 K 小的数对距离 困难 二分距离，计数改用排序后的双指针而不是阶梯走法
215. 数组中的第K个最大元素 中等 无序数组求第 $k$ 大，主流解是快速选择而非值域二分
LCR 061. 查找和最小的 K 对数字 中等 与 373 同题，堆中只需放入每个左元素当前配对的右下标