fork download
copy 
  1. #include <queue>
  2. #include <iostream>
  3. #include <functional>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. vector<pair<int, int>> kSmallestPairs(const vector<int>& nums1, const vector<int>& nums2, int k) {
  9.     vector<pair<int, int>> ans;
  10.     int m = nums1.size();
  11.     if(m == 0) return ans;
  12.     int n = nums2.size();
  13.     if(n == 0) return ans;
  14.     priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(const pair<int,int>&, const pair<int,int>&)>> pq([&](const pair<int,int>&a, const pair<int,int>&b){
  15.         return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
  16.     });
  17.     pq.push({0, 0});
  18.  
  19.     while(!pq.empty() && k-- > 0) {
  20.         auto top = pq.top();
  21.         pq.pop();
  22.         int index1 = top.first, index2 = top.second;
  23.         ans.push_back({nums1[index1], nums2[index2]});
  24.         if(index1 + 1 < m) pq.push({index1 + 1, index2});
  25.         if(index2 + 1 < n) pq.push({index1, index2 + 1});
  26.     }
  27.     return ans;
  28. }
  29.  
  30. int main()
  31. {
  32.     for (const auto& p : kSmallestPairs({1,7,11}, {2,4,6}, 3)) {
  33.         std::cout << p.first << ", " << p.second << std::endl;        
  34.     }
  35. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1, 2
1, 4
1, 6
https://ideone.com/QI8GGY
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!