【leetcode】378. Kth Smallest Element in a Sorted Matrix（TOP k 问题）

　　Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with complexity better than O(n2).

　　Example 1:

　　Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

　　构建一个优先队列，底层是一个大顶堆，最大的元素会排在前面，同时维护这个优先队列的长度为k，从而可以得到第k小的元素如果是小顶堆的话，需要传入仿函数，构造新的排序准则，从而得到第k大的元素。

class Solution {

public:

    int kthSmallest(vector<vector<int>>& matrix, int k) {

        priority_queue<int> dp;

        for(int i=0;i<matrix.size();++i){

            for(int j=0;j<matrix[0].size();++j){

                dp.push(matrix[i][j]);

                if(dp.size()>k) dp.pop();

            }

        }

        return dp.top();

    }

};

巴特西

【leetcode】378. Kth Smallest Element in a Sorted Matrix（TOP k 问题）

最新文章

热门文章