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

Categories:

Tags:

题目描述
思路分析
1. 解法一：二分答案（推荐）
2. 解法二：最小堆（多路归并）
相似题目

题目描述

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

思路分析

解法一：二分答案（推荐）

核心思路：

矩阵中每行每列均升序，最小值为 matrix[0][0]，最大值为 matrix[n-1][n-1]，以此作为二分的左右边界。

二分猜测答案 mid，统计矩阵中 <= mid 的元素个数 count：

若 count < k，说明第 k 小的元素比 mid 大，缩小左边界：left = mid + 1。

否则，缩小右边界：right = mid。

统计 <= mid 的个数时，利用矩阵有序性从左下角出发：当前元素 <= mid 则整列上方均满足，计入 row + 1 个并向右移；否则向上移。

循环结束时 left 一定是矩阵中存在的元素，即为第 k 小的答案。

复杂度分析：

时间复杂度：O(n log(max - min))，其中 n 为矩阵边长，max/min 为矩阵最大/最小值，每次二分需 O(n) 统计。

空间复杂度：O(1)，仅使用常数额外空间。

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;
            // 统计矩阵中 <= mid 的元素个数
            if (countLessEqual(matrix, mid, n) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    // 从左下角出发，统计 <= mid 的元素个数
    private int countLessEqual(int[][] matrix, int mid, int n) {
        int count = 0;
        int row = n - 1;
        int col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // 当前列从 0 到 row 均 <= mid
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}

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

    for left < right {
        mid := left + (right-left)/2
        // 统计矩阵中 <= mid 的元素个数
        if countLessEqual(matrix, mid, n) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
}

// countLessEqual 从左下角出发统计 <= mid 的元素个数
func countLessEqual(matrix [][]int, mid, n int) int {
    count := 0
    row, col := n-1, 0
    for row >= 0 && col < n {
        if matrix[row][col] <= mid {
            // 当前列从 0 到 row 均 <= mid
            count += row + 1
            col++
        } else {
            row--
        }
    }
    return count
}

解法二：最小堆（多路归并）

核心思路：

将矩阵每行视为一个有序链，共 n 路有序序列，使用最小堆合并。

初始将每行第一个元素（行索引、列索引、值）入堆。

每次弹出堆顶最小元素，若该元素所在行还有下一列，则将下一个元素入堆。

重复 k 次，第 k 次弹出的堆顶即为第 k 小的元素。

复杂度分析：

时间复杂度：O(k log n)，其中 n 为矩阵边长，堆大小始终为 n，共弹出 k 次。

空间复杂度：O(n)，堆中最多存储 n 个元素。

class Solution {

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // 最小堆：存储 [值, 行, 列]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // 将每行第一个元素入堆
        for (int i = 0; i < n; i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }

        // 弹出 k-1 次，第 k 次弹出的即为答案
        for (int i = 0; i < k - 1; i++) {
            int[] top = minHeap.poll();
            int row = top[1];
            int col = top[2];
            // 若当前行还有下一个元素，则入堆
            if (col + 1 < n) {
                minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
            }
        }

        return minHeap.poll()[0];
    }
}

import "container/heap"

// element 表示堆中的元素
type element struct {
    val, row, col int
}

type minHeap []element

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].val < h[j].val }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(element)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    h := &minHeap{}
    heap.Init(h)

    // 将每行第一个元素入堆
    for i := 0; i < n; i++ {
        heap.Push(h, element{val: matrix[i][0], row: i, col: 0})
    }

    // 弹出 k-1 次，第 k 次弹出即为答案
    for i := 0; i < k-1; i++ {
        top := heap.Pop(h).(element)
        // 若当前行还有下一个元素，则入堆
        if top.col+1 < n {
            heap.Push(h, element{val: matrix[top.row][top.col+1], row: top.row, col: top.col + 1})
        }
    }

    return heap.Pop(h).(element).val
}

相似题目

题目	难度	考察点
719. 找出第 K 小的数对距离	困难	二分查找、滑动窗口计数
668. 乘法表中第 k 小的数	困难	二分查找、矩阵计数
786. 第 K 个最小的素数分数	中等	二分查找 / 最小堆
373. 查找和最小的 K 对数字	中等	最小堆、多路合并
1439. 有序矩阵中的第 k 个最小数组和	困难	最小堆、多路合并
240. 搜索二维矩阵 II	中等	有序矩阵性质、行列排除

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/32635930