第373题---Find K Pairs with Smallest Sums

• 题意描述
  • 给定两个数组，从小到达排列，两个数组中的元素组成一对，按两个数的和从大到小排序，找到前k个最小的pair
    
    
• 思路
  • 没思路，完全copy，代码的写法比较有意思
    
    
• 代码

  class Solution {
  public:
      vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
          vector<pair<int, int>> result;
          if(nums1.empty() || nums2.empty() || k <= 0)
              return result;
          auto comp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) {
              return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
          };
          priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> min_heap(comp);
          min_heap.emplace(0, 0);
          while(k -- > 0 && min_heap.size()) {
              auto idx_pair = min_heap.top();
              min_heap.pop();
              result.emplace_back(nums1[idx_pair.first], nums2[idx_pair.second]);
              if(idx_pair.first + 1 < nums1.size())
                  min_heap.emplace(idx_pair.first + 1, idx_pair.second);
              if(idx_pair.first == 0 && idx_pair.second + 1 < nums2.size())
                  min_heap.emplace(idx_pair.first, idx_pair.second + 1);
          }
          return result;
      }
  };