网站设计与管理教程,会计公司网站模板,代码编程教学入门软件,信息化网站建设有什么用优先队列
思路#xff1a; 使用下标 (x, y) 标识数值对#xff0c;x 为第一个数组的下标#xff0c;y 为第二个数组的下标#xff1b;所以 k 个数值对 x 的范围属于 [0, min(k, m)]#xff0c;m 为第一个数组的 size#xff1b;数值对 (x, y) #xff0c;那么下一个比其…优先队列
思路 使用下标 (x, y) 标识数值对x 为第一个数组的下标y 为第二个数组的下标所以 k 个数值对 x 的范围属于 [0, min(k, m)]m 为第一个数组的 size数值对 (x, y) 那么下一个比其大的数组对是 min{(x, y 1), (x 1, y)}可以先固定 x 即将 x 可能的值全选来动态变更 y构建一个优先队列存放的是 (x, y)小顶堆即其对应的数值对的和最小的总是在堆顶nums1[a.first] nums2[a.second] nums1[b.first] nums2[b.second];将小顶堆取 k 次堆顶即可每次之后将 (x, y 1) 入堆即可
class Solution {
public:vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) {auto cmp [nums1, nums2](const std::pairint, int a, const std::pairint, int b) {return nums1[a.first] nums2[a.second] nums1[b.first] nums2[b.second];};int m nums1.size();int n nums2.size();std::vectorstd::vectorint result;std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp);for (int i 0; i std::min(k, m); i) {pq.emplace(i, 0);}while (k-- 0 !pq.empty()) {auto [x, y] pq.top();pq.pop();result.push_back(std::initializer_listint{nums1[x], nums2[y]});if (y 1 n) {pq.emplace(x, y 1);}}return result;}
};
