c++ priority_queue solution


  • 18
    S

    nums1: m nums2: n
    time complexity: O(m * n logk)
    space complexity O(k)

    72ms solution:

    class Solution {
    private:
        struct mycompare{
            bool operator()(pair<int, int>& p1, pair<int, int>& p2){
                return p1.first + p1.second < p2.first + p2.second;
            }
        };
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> res;
            priority_queue<pair<int,int>, vector<pair<int, int> >, mycompare> pq;
            for(int i = 0; i < min((int)nums1.size(), k); i++){
                for(int j = 0; j < min((int)nums2.size(), k); j++){
                    if(pq.size() < k)
                        pq.push(make_pair(nums1[i], nums2[j]));
                    else if(nums1[i] + nums2[j] < pq.top().first + pq.top().second){
                        pq.push(make_pair(nums1[i], nums2[j]));
                        pq.pop();
                    }
                }
            }
            while(!pq.empty()){
                res.push_back(pq.top());
                pq.pop();
            }
            return res;
        }
    };
    

    1132ms solution:

    class Solution {
    private:
        struct mycompare{
            bool operator()(pair<int, int>& p1, pair<int, int>& p2){
                return p1.first + p1.second < p2.first + p2.second;
            }
        };
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> res;
            priority_queue<pair<int,int>, vector<pair<int, int> >, mycompare> pq;
            for(int num1 : nums1){
                for(int num2 : nums2){
                    pq.push(make_pair(num1, num2));
                    if(pq.size() > k) pq.pop();
                }
            }
            while(!pq.empty()){
                res.push_back(pq.top());
                pq.pop();
            }
            return res;
        }
    };
    

    40ms solution:

    class Solution {
    public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> res;
            int m = (int)nums1.size();
            int n = (int)nums2.size();
            k = min(k, m * n);
            vector<int> indice(m, 0);
            while(k-- > 0){
                int tmp_index = 0;
                long tmp_sum = LONG_MAX;
                for(int i = 0; i < m; i++){
                    if(indice[i] < n && tmp_sum >= nums1[i] + nums2[indice[i]]){
                        tmp_index = i;
                        tmp_sum = nums1[i] + nums2[indice[i]];
                    }
                }
                res.push_back(make_pair(nums1[tmp_index], nums2[indice[tmp_index]]));
                indice[tmp_index]++;
            }
            return res;
        }
    };
    

  • 0
    D

    In my opinion,the time complexity showed as follows:
    nums1: m nums2: n
    method1:O(mim(m,k) mim(n,k)logk)
    method2:O(m
    n
    logk)
    method3:O(min(k,m*n)*min(m,n))
    am i right?


  • 0
    S

    I think this version of implementation of minimum heap is much easier to be understood than that of @fentoyal.


  • 0
    I
                    pq.push(make_pair(num1, num2));
                    if(pq.size() > k) pq.pop();
    

    i am confused about this code snippet..
    wouldn't it pop the smallest one? but actually we want the smallest one in queue.


  • 0

    @iceman2369 priority_queue container defaults to a max queue I believe


  • 0
    P

    @sxycwzwzq, please do you mind explaining your 40ms solution? I've been trying to follow it all day now and don't quite understand the logic. Greedy algorithms are one of my weak areas and I'm trying to get better.


  • 0
    T

    the 40ms solution is sooooooooooo fabulous!


  • 0
    D

    If we use make_heap and pop_heap, it can run fast at 32 ms.

    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int n1 = nums1.size(), n2 = nums2.size();
            vector<pair<int, int>> h;
            vector<pair<int, int>> res;
            for (int i = 0; i < n1; i++)
            {
                for (int j = 0; j < n2; j++)
                {
                    h.emplace_back(nums1[i], nums2[j]);
                }
            }
            auto comp = [](pair<int, int>& a, pair<int, int>& b) {
                return a.first + a.second > b.first + b.second;
            };
            make_heap(h.begin(), h.end(), comp);
            while(k-- && !h.empty())
            {
                pop_heap(h.begin(), h.end(), comp);
                res.push_back(h.back());
                h.pop_back();
            }
            return res;
        }
    };
    

Log in to reply
 

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