C++ Solution by Creating a Node Structure for heap


  • 1
    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;
    }

  • 0
    J

    hey, bloomer,

    After being inspired by someone else, I implemented similar solution, but this solution may not go through matrix[nums1.size()-1][nums2.size()-1].

    class Node{
    public:
        int x;
        int y;
        int sum;
        Node(int x, int y, int sum): x(x), y(y), sum(sum){}
    };
    
    class Compare{
    public:
        bool operator() (Node n1, Node n2) {return n1.sum > n2.sum;}
    };
    
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> ret;
            vector<vector<bool>> record(nums1.size(), vector<bool>(nums2.size(), true));
            priority_queue<Node, vector<Node>, Compare> min_heap;
            
            if (nums1.empty() || nums2.empty() || !k) return ret;
            
            min_heap.push(Node(0, 0,nums1[0]+nums2[0]));
            
            // get min and add candidates
            for (int i=1; i<=k; i++){
                if (min_heap.empty()) break;
                Node cur = min_heap.top(); min_heap.pop();
                ret.push_back(pair<int,int>(nums1[cur.x], nums2[cur.y]));
                if (cur.x+1<nums1.size() && record[cur.x+1][cur.y]) {
                    record[cur.x+1][cur.y] = false;
                    min_heap.push(Node(cur.x+1, cur.y, nums1[cur.x+1]+nums2[cur.y]));
                }
                if (cur.y+1<nums2.size() && record[cur.x][cur.y+1]) {
                    record[cur.x][cur.y+1] = false;
                    min_heap.push(Node(cur.x, cur.y+1, nums1[cur.x]+nums2[cur.y+1]));
                }
            }
            
            return ret;
        }
    };
    

Log in to reply
 

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