373 查找和最小的 K 对数字
可转换为合并k条有序链表: - 第一条链表: nums1[0]作为数对的第一个元素,剩余nums2的元素作为数对的第二个元素 - 第二条链表: nums1[1]作为数对的第一个元素,剩余nums2的元素作为数对的第二个元素 - 以此类推,总共nums1.size()条链表 - 接着合并这些链表即可
class Solution {
public:
struct State{
int u;
int v;
int pv;
};
struct cmp{
bool operator() (const State& s1, const State& s2) const{
return (s1.u + s1.v) > (s2.u + s2.v);
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<State, vector<State>, cmp> heap;
for(int i = 0; i < nums1.size(); i++){
heap.push(State(nums1[i], nums2[0], 0));
}
vector<vector<int>> res;
while(k > 0 && !heap.empty()){
State s = heap.top();
heap.pop();
res.push_back({s.u,s.v});
if(s.pv + 1 < nums2.size()){
heap.push(State(s.u, nums2[s.pv + 1], s.pv + 1));
}
k--;
}
return res;
}
};