Concise AC C++ solution using priority_queue


  • 0
    W

    Just the same idea as the problem "find k pairs with smallest sums" using priority queue.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            auto compare = [&matrix](pair<int, int> a, pair<int, int> b){
                return matrix[a.first][a.second] > matrix[b.first][b.second];
            };
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> min_heap(compare);
            int m = matrix.size();
            int n = matrix[0].size();
            for(int i=0;i<m;i++)
                min_heap.emplace(i, 0);
            int res;
            for(int i=0;i<k;i++){
                auto temp = min_heap.top();
                res = matrix[temp.first][temp.second];
                min_heap.pop();
                if(temp.second < n-1)
                    min_heap.emplace(temp.first, temp.second+1);
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.