373 Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

• Example 1:

  Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
  Return: [1,2],[1,4],[1,6]
  

  The first 3 pairs are returned from the sequence:

  [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
  

• Example 2:

  Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
  Return: [1,1],[1,1]
  

  The first 2 pairs are returned from the sequence:

  [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
  

• Example 3:

  Given nums1 = [1,2], nums2 = [3],  k = 3 
  Return: [1,3],[2,3]
  

  All possible pairs are returned from the sequence:

  [1,3],[2,3]
  

  Notes
  Originally I want to solve this problem using two pointers. But later I found that we will miss certain pairs.
• Use heap (priority_queue) to solve the problem.
• (It is a derivation of topK problem.)

class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<pair<int, int>> record;
        int n1 = nums1.size(), n2 = nums2.size();
        vector<pair<int, int>> res;
        if ( n1 == 0 or n2 == 0 ) return res;
        for ( int i1 = 0; i1 <= n1-1; i1++ ) {
            for ( int i2 = 0; i2 <= n2-1; i2++ ) {
                if ( record.size() <= k-1 ) {record.push(pair<int, int>(nums1[i1]+nums2[i2], nums2[i2])); continue;}
                if ( nums1[i1] + nums2[i2] >= record.top().first )  continue;
                record.push(pair<int, int>(nums1[i1]+nums2[i2], nums2[i2]));
                record.pop();
            }
        }
        while ( record.size() != 0 ) {
            auto tmp = record.top();
            record.pop();
            res.push_back(pair<int, int>(tmp.first-tmp.second, tmp.second));
        }
        reverse(res.begin(), res.end());
        return res;
    }
};