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;
}
};