LeetCode笔记：378. Kth Smallest Element in a Sorted Matrix

Cloudox

发布于 2021-11-23 15:38:56

1730

发布于 2021-11-23 15:38:56

问题：

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example:

image.png k = 8, return 13. Note: You may assume k is always valid, 1 ≤ k ≤ n2.

大意：

给出一个 n * n的矩阵，每一行每一列都是升序的，找到矩阵中第 k 小的元素。注意是整个顺序第 k 小的数，不是第 k 个元素。例：

image.png k = 8, 返回 13。注意：你可以假设 k 始终有效，1 ≤ k ≤ n2。

思路：

题目给出的矩阵只是每一行和每一列是升序的，但是一个元素的下一个行元素和下一个列元素之间的大小是不定的。

我们要找第 k 小的元素，那么用一个 k 遍的循环来从小开始找。

我们用一个数组来记录每行现在前多少个元素已经记录过了，当前要找的时候从这一行第几个元素开始找，不过要注意如果这一行都找完了就不找了。

每次找当前最小值的时候都从这一行的当前该找的位置开始，这个位置可能每一行都是不同的，找到最小的记录下来，就是这一轮找到最小的数。一直到第 k 轮找到的最小的数就是我们要的结果。

代码（Java）：

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int[] index = new int[matrix.length];
        int pos = 0;
        int small = matrix[matrix.length-1][matrix[0].length-1];;
        for (; k > 0; k--) {
            small = matrix[matrix.length-1][matrix[0].length-1];
            for (int i = 0; i < matrix.length; i++) {
                if (index[i] >= matrix[i].length) continue;
                if (matrix[i][index[i]] <= small) {
                    small = matrix[i][index[i]];
                    pos = i;
                }
            }
            index[pos]++;
        }
        return small;
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017/11/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

element