C++ Solution by Creating a Node Structure for heap


  • 0
    B

    struct HeapNode{

        int sum;
        pair<int,int> pr;
    };
    
    struct compare{
        
        bool operator()(HeapNode* hn1, HeapNode* hn2){
            return hn1->sum > hn2->sum;
        }  
    };
    
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int> > res;
         priority_queue<HeapNode*, vector<HeapNode*> , compare > pq;
        for(int i = 0; i < min(k,(int)nums1.size()); i++){
            for(int j  = 0; j < min(k,(int)nums2.size()); j++){
                
                int sum = nums1[i] + nums2[j];
                pair<int, int> pr;
                pr = make_pair(nums1[i],nums2[j]);
                HeapNode* hn = new HeapNode();
                hn->sum = sum;
                hn->pr = pr;
                pq.emplace(hn);
            }
         }
        
       
        
        while(k-- && !pq.empty()){
            HeapNode* node = pq.top();
            
            res.emplace_back(make_pair(node->pr.first,node->pr.second));
            pq.pop();
        }
        
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.