c++ using heap


  • 0
    X
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int xsize = matrix.size();
            int ysize = matrix[0].size();
            priority_queue<Node, vector<Node>, Cmp> pq;
            pq.push(Node(matrix[0][0], 0, 0));
            Node tmp(-1, -1, -1);
            while(k--){
                tmp = pq.top();
                pq.pop();
                if(tmp.i + 1 < xsize){
                    pq.push(Node(matrix[tmp.i + 1][tmp.j], tmp.i + 1, tmp.j));
                }
                if(tmp.i == 0 && tmp.j + 1 < ysize){
                    pq.push(Node(matrix[tmp.i][tmp.j + 1], tmp.i, tmp.j + 1));
                }
            }
            return tmp.val;
        }
    private:
        struct Node {
            int val;
            int i;
            int j;
            Node(int vv, int ii,  int jj): val(vv), i(ii), j(jj){};
        };
        struct Cmp {
            bool operator()(const Node& a, const Node& b){
                return a.val > b.val;
            }
        };
    };
    

  • 0
    Q

    Question,
    why you only push the right neighbor into the priority queue only when i==0? What bad thing would happen if you push it any way? Thanks.


  • 0

    @quesder
    The reason for that is if you do not restrict only when i == 0 that you can push the right neighbor, you may push the same elements for twice. Say, the element can be push by its upper neighbor, and then by its left neighbor.

    Consider this example:
    1 3 5
    6 7 12
    11 14 14


Log in to reply
 

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