C++ solution same as Find K pairs with smaller sums


  • 5
    M

    class Solution {
    public:

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        auto comp = [&matrix](pair<int, int> p1, pair<int, int> p2){
            return matrix[p1.first][p1.second] > matrix[p2.first][p2.second];
        };
        priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(comp)> que(comp);
        que.push(make_pair(0, 0));
        int count = 1;
        while(count < k){
             auto temp = que.top();
             que.pop();
             if(temp.first+1 < matrix.size()){
                 que.push(make_pair(temp.first+1, temp.second));
             }
             if(temp.first == 0 && temp.second+1 < matrix[0].size()){
                 que.push(make_pair(temp.first, temp.second+1));
             }
             count++;
        }
        auto t = que.top();
        return matrix[t.first][t.second];
    }
    

    };


  • 0

    @MichaelJiang Same solution as mine.

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        auto comp = [&matrix](const pair<int, int>& p1, const pair<int, int>& p2){
            return matrix[p1.first][p1.second] > matrix[p2.first][p2.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
        pq.emplace(0, 0);
        for (int i = 1; i < k; ++i) {
            auto p = pq.top(); pq.pop();
            if (p.second + 1 < n) {
                pq.emplace(p.first, p.second+1);
            }
            if (p.second == 0 && p.first + 1 < m) {
                pq.emplace(p.first + 1, 0);
            }
        }
        auto p = pq.top();
        return matrix[p.first][p.second];
    }

Log in to reply
 

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