leetcode378-有序矩阵中第K小的元素

原题

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。
请注意,它是排序后的第k小元素,而不是第k个元素。

示例:

matrix = [
  [ 1, 5, 9],
  [10, 11, 13],
  [12, 13, 15] ],
k = 8,

返回 13。

说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2

解法

思想

使用最大堆求topk

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        Queue<Integer> queue = new PriorityQueue<>((o1,o2)->o2-o1);
        int width = matrix.length;
        for(int i = 0;i<width;i++){
            for(int j = 0;j<width;j++){
                queue.offer(matrix[i][j]);
            }
        }
        while(queue.size()>k) queue.poll();
        return queue.peek();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode378-%e6%9c%89%e5%ba%8f%e7%9f%a9%e9%98%b5%e4%b8%ad%e7%ac%ack%e5%b0%8f%e7%9a%84%e5%85%83%e7%b4%a0/

发表评论

电子邮件地址不会被公开。