利用heap+map求解
class Solution { public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<pair<int, int>> result; map<int,vector<pair<int, int>>> func; std::priority_queue<int, std::vector<int>, std::greater<int> > allSums; for(int i=0;i<nums1.size();i++) { for(int j=0;j<nums2.size();j++) { int sum=nums1[i]+nums2[j]; allSums.push(sum); pair<int,int> temp(nums1[i],nums2[j]); func[sum].push_back(temp); } } while(!(allSums.empty()||k==0)) { int small=allSums.top(); if(func[small].size()>=k) { for(int i=0;i<k;i++) result.push_back(func[small][i]); k=0; } else { for(int i=0;i<func[small].size();i++) result.push_back(func[small][i]); k-=func[small].size(); } allSums.pop(); while((!allSums.empty())&&allSums.top()==small) allSums.pop(); } return result; } };