Leetcode刷题java之378. 有序矩阵中第K小的元素（一天一道编程题之二十五天）

一时失言乱红尘 2023-07-15 09:08 17阅读 0赞

执行结果：

通过

显示详情

执行用时 :22 ms, 在所有 Java 提交中击败了33.63% 的用户

内存消耗 :46.1 MB, 在所有 Java 提交中击败了6.18%的用户

题目：

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

示例:

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

返回 13。

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

未获一个大小为k的优先队列，采用大顶堆。

大顶堆获取最小的k个数，因为每次都出去最大的。

小顶堆获取最大的k个数，因为每次都是出去最小的。

代码：

class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
                public int compare(Integer a,Integer b)
                {
                    return b-a;
                }
            });
            for(int i=0;i<matrix.length;i++)
            {
                for(int j=0;j<matrix[0].length;j++)
                {
                    queue.add(matrix[i][j]);
                    if(queue.size()>k)
                    {
                        queue.poll();
                    }
                }
            }
            return queue.poll();
        }
    }