leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0373.cpp (689B)

      1 class Solution {
      2     typedef tuple<int, int, int> tpl;
      3 
      4   public:
      5     vector<vector<int>> kSmallestPairs(const vector<int> &nums1, const vector<int> &nums2, int k) {
      6         priority_queue<tpl, vector<tpl>, greater<tpl>> pq;
      7         vector<vector<int>> res;
      8         res.reserve(k);
      9 
     10         for (int i = 0; i < min(k, (int)nums1.size()); i++)
     11             pq.push({nums1[i] + nums2[0], i, 0});
     12 
     13         while (k-- && !pq.empty()) {
     14             auto [sum, i, j] = pq.top();
     15             pq.pop();
     16             res.push_back({nums1[i], nums2[j]});
     17             if (j == nums2.size() - 1) continue;
     18             pq.push({nums1[i] + nums2[j + 1], i, j + 1});
     19         }
     20         return res;
     21     }
     22 };