373. 查找和最小的 k 对数字（堆priority_queue）

张开发
• 2026/4/11 12:29:16 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

373. 查找和最小的 k 对数字（堆priority_queue）
链接固定num2想象为多个数组合并https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/description/https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envTypestudy-plan-v2envIdtop-interview-150class Solution { public: struct Node { int i; // nums1的索引 int j; // nums2的索引 int sum; // 缓存和值避免重复计算 Node(int row, int col, int s) : i(row), j(col), sum(s) {} bool operator(const Node a) const { return sum a.sum; // 最小堆 } }; vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) { if (nums1.empty() || nums2.empty() || k 0) return {}; priority_queueNode que; // 初始化将nums1中前min(k, nums1.size())个元素与nums2[0]配对 for (int i 0; i min(k, (int)nums1.size()); i) { que.push(Node(i, 0, nums1[i] nums2[0])); } vectorvectorint result; while (k-- 0 !que.empty()) { Node curr que.top(); que.pop(); result.push_back({nums1[curr.i], nums2[curr.j]}); // 将同一行的下一个元素加入堆 if (curr.j 1 nums2.size()) { que.push(Node(curr.i, curr.j 1, nums1[curr.i] nums2[curr.j 1])); } } return result; } };

更多文章