题目描述
合并n个有序数组
思路
- 利用堆
- 优先级队列
- 第一种实现自定义的priority_queue 可以使用运算符重载 重载小于运算符
- 第二种是利用放函数 类似与 less
从大到小,greater 从小到大 一样， - 仿函数是类，然后重载()进行比较即可
struct Elem{
int row;
int col;
int val;
Elem(int row, int col, int val){
this -> row = row;
this -> col = col;
this -> val = val;
}
// 第一种是运算符重载
bool operator<(const Elem& oth) const { // 需要加const 不然就调用默认的函数 够不成
return this -> val > oth.val; // 实现 小顶堆
}
};
// 仿函数是类
// 第二种是写仿函数 重载()进行比较 默认为public
struct cmp2{
bool operator()(Elem e1, Elem e2){
return e1.val > e2.val;
}
};
// 重写仿函数 默认为private 需要显著表明
class cmp2{
public:
bool operator()(Elem e1, Elem e2){
return e1.val > e2.val;
}
};
vector<int> mergeList(vector<vector<int>> lists){
priority_queue<Elem, vector<Elem>, cmp2> q; // 显示使用仿函数
// priority_queue<Elem> q; // 默认的使用运算符重载
int r = (static_cast<int>(lists.size()));
for(int i = 0; i < r; i++){
q.push(Elem(i, 0, lists[i][0]));
}
vector<int> res;
while(!q.empty()){
Elem elem = q.top();
int temp_r = elem.row;
int temp_c = elem.col;
res.push_back(elem.val);
q.pop();
if(temp_c + 1 < lists[temp_r].size()){
q.push(Elem(temp_r, temp_c + 1, lists[temp_r][temp_c + 1]));
}
}
return res;
}
