首页 > 其他 > 详细

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

时间:2019-11-04 21:24:49      阅读:148      评论:0      收藏:0      [点我收藏+]

1.题目描述:

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

  题目链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

 

2.解题思路及代码:

  构造一个最多容纳m个元素的优先队列,遍历矩阵,将矩阵的值加入优先队列中,若优先队列元素超过m,则将队首弹出,由于java优先队列默认升序排列,遍历结束后队首便是第m大的元素。

  题目要求求第k小元素,即第n*n-k+1大的元素

  代码如下:

  

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int num=matrix.length*matrix[0].length-k+1;
        Queue<Integer> q = new PriorityQueue<>();
        for(int i=0;i<matrix.length;i++) {
            for(int j=0;j<matrix[0].length;j++) {
                q.add(matrix[i][j]);
                if(q.size()>num)
                    q.poll();
            }
        }
        return q.peek();
    }
}

 

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

原文:https://www.cnblogs.com/teensSpirit-code-life/p/11794285.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!