C++ priority queue


  • 0
    class Solution {
        struct comp {
            bool operator()(const vector<int>& a, const vector<int>& b) {
                return a[0] > b[0];
            };
        };
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int m = matrix.size();
            if(m==0) return 0;
            int n = matrix[0].size();
            if(n==0) return 0;
            int cnt = 0;
            priority_queue<vector<int>,vector<vector<int>>,comp> pq;
            pq.push({matrix[0][0],0,0});
            vector<vector<int>> visited(m,vector<int>(n,0));
            visited[0][0] = 1;
            while(cnt<k) {
                auto p = pq.top();
                pq.pop();
                cnt ++;
                if(cnt==k) return p[0];
                int i = p[1];
                int j = p[2];
                if(i+1<m && visited[i+1][j]==0) {
                    pq.push({matrix[i+1][j],i+1,j});
                    visited[i+1][j]=1;
                }
                if(j+1<n && visited[i][j+1]==0) {
                    pq.push({matrix[i][j+1],i,j+1});
                    visited[i][j+1]=1;
                }
            }
            return 0;
        }
    };
    

Log in to reply
 

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