優先隊列
- 思路:
- 使用下標 (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:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {auto cmp = [&nums1, &nums2](const std::pair<int, int>& a, const std::pair<int, int>& b) {return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];};int m = nums1.size();int n = nums2.size();std::vector<std::vector<int>> result;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, 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_list<int>{nums1[x], nums2[y]});if (y + 1 < n) {pq.emplace(x, y + 1);}}return result;}
};