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

约 6 分钟
文章信息 14 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 未掌握 20-50 腾讯 字节 亚马逊 美团 拼多多 快手 滴滴 虾皮
标签
数组 排序 二分查找 矩阵 堆（优先队列）

题目描述

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

image-20260928200301016

image-20260928200301017

题意分析

给定每行、每列都按非递减顺序排列的方阵，求把全部元素按从小到大排列后位于第 k 个的值，名次从一开始。重复值按出现次数分别占名次，不能先去重。

行列各自有序不代表把各行首尾拼接后整体有序，所以不能直接把第 k 个位置当成答案。只需返回数值，不需要真正生成排序后的序列。

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

核心思路

[!blue]

对候选值 x，定义 count(x) 为矩阵中不大于它的元素数量。如果数量小于 k，第 k 小必定比 x 大；如果数量至少为 k，第 k 小不会大于 x。这个数量随 x 单调不减，因此可以在左上角最小值到右下角最大值之间二分，寻找第一个数量达到 k 的整数。

判定时不必逐个扫描全部格子。从左下角出发，当前位置同时是尚未处理部分的本列最大值、本行最小值。若它不大于 x，同列上方的 row + 1 个值都合格，可以一起计数，再进入下一列；若它大于 x，同一行右边的值只会更大，都不合格，于是向上移动一行。

指针只会上移或右移。已经跳过的下方行，在后续更靠右的列里仍然过大，不需要回头检查；每次计数都对应新的一列，所以不会重复。最多移动约 2n 次，就能得到准确的 count(x)。

数量足够时令 right = mid，因为中点本身可能就是答案；数量不足时令 left = mid + 1。二分中点不一定出现在矩阵中，但最终最小可行值一定出现过：若它不存在，把它减一并不会减少计数，就与“最小可行”矛盾。重复值导致计数跳跃，也不影响寻找这个边界。

解题步骤

  1. 将值域下界设为左上角元素，上界设为右下角元素。
  2. 在两界未相遇时取中点 mid，从左下角开始统计不大于 mid 的元素数量。
  3. 当前元素合格时，加上 row + 1 并右移一列；当前元素过大时，上移一行，直到走出矩阵边界。
  4. 计数至少为 k，将上界改为 mid；否则将下界改为 mid + 1。
  5. 两界相遇时，返回该值。

代码实现

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 = 最大值 - 最小值 + 1 为候选整数数量。值域每轮缩小约一半，每次阶梯计数为 $O(n)$；值域只有一个值时直接返回。
  • 空间复杂度：$O(1)$，只使用值域边界、扫描位置和计数器，不展开矩阵。

关键点总结

[!green]

  • 二分对象是答案数值，判定问题是“已有至少 k 个值不超过它吗”。
  • 行列有序让一次比较能统计一列的整段，或者排除一行的剩余部分。
  • 寻找第一个可行值，数量足够时要保留中点，不能提前返回任意可行数。
  • 重复值分别计数，边界查找能够直接处理计数一次增加多个名次的情况。

易错点总结

[!yellow]

  • 将按行展开的数组当作整体有序，忽略下一行的首元素可能小于上一行尾元素。
  • 只计算严格小于候选值的数量，或者要求数量严格大于 k，都会偏离当前二分判定定义。
  • 数量足够时使用 right = mid - 1，可能排除答案；不足时使用 left = mid，相邻边界可能无法收缩。
  • 当前值合格却向下移动，或者过大仍右移，破坏了左下角计数的排除方向。
  • 每次右移都把行号重置到底部，会失去阶梯扫描的线性计数优势。
  • 对重复值去重后计数，改变了原题按出现次数定义的第 k 小。

相似题目

题目 难度 关联与区别
373. 查找和最小的 K 对数字 中等 两数组数对和构成隐式有序矩阵，原题输出前k个数对，本题只求第k小值。
668. 乘法表中第k小的数 困难 按截止值统计不大于候选的数量以二分第 k 小；本题在行列有序矩阵内计数，该题按乘法表的每行计数。
719. 找出第 K 小的数对距离 困难 按截止值统计不大于候选的数量以二分第 k 小；本题在行列有序矩阵内计数，该题排序后用双指针统计不超过候选的数对距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/32635930
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！