跳转至

378 有序矩阵中第 K 小的元素

每一行看作一条有序链表,那么本题转换为合并k条有序链表

题意给出n x n,因此一共有n条有序链表,每条有序链表长度为n

class Solution {
public:
    struct State{
        int val;
        int i;
        int j;
        State(){}
        State(int _val, int _i, int _j): val(_val), i(_i), j(_j){}
    };
    struct cmp{
        // minHeap
        bool operator() (const State& s1, const State& s2) const{
            return s1.val > s2.val;
        }
    };
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<State,vector<State>,cmp> heap;
        for(int i = 0; i < n; i++){
            heap.push(State(matrix[i][0], i, 0));
        }
        int res = -1;
        while(k > 0 && !heap.empty()){
            State s = heap.top();
            heap.pop();
            res = s.val;
            if(s.j + 1 < n){
                heap.push(State(matrix[s.i][s.j + 1], s.i, s.j + 1));
            }
            k--;
        }
        return res;
    }
};