Skip to content

Instantly share code, notes, and snippets.

@theidexisted

theidexisted/get_priority_queue_cont.cpp

Created July 17, 2016 12:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save theidexisted/5bbe3f2046184aff130bd26200770589 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save theidexisted/5bbe3f2046184aff130bd26200770589 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. theidexisted created this gist Jul 17, 2016.
    48 changes: 48 additions & 0 deletions get_priority_queue_cont.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,48 @@
    // https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
    // a brute-force solution, just for demonstration how to get container from priority_queue

    template <class T,
    class Container = vector<T>,
    class Compare = less<typename Container::value_type> >
    class priority_queue_v2 : public priority_queue<T, Container, Compare> {
    public:
    using base_t = priority_queue<T, Container, Compare>;
    priority_queue_v2(const Compare& cmp)
    : base_t(cmp) {
    }
    const Container& get_underline_container() const {
    return priority_queue<T, Container, Compare>::c;
    }
    };

    class Solution {
    public:
    vector<pair<int, int>> kSmallestPairs(vector<int> nums1, vector<int> nums2, int k) {
    using pair_t = std::pair<int, int>;
    auto cmp = [](const pair_t& lhs, const pair_t& rhs) {
    return lhs.first + lhs.second < rhs.first + rhs.second;
    };

    priority_queue_v2<pair_t, std::vector<pair_t>, decltype(cmp)> pq(cmp);

    size_t i = 0, sz = nums2.size();
    for (const auto v1: nums1) {
    for (i = 0; i < sz; ++i) {
    int v2 = nums2[i];
    if (pq.size() < k) {
    pq.emplace(v1, v2);
    continue;
    }
    const auto& top_v = pq.top();
    if (v1 + v2 < top_v.first + top_v.second) {
    pq.pop();
    pq.emplace(v1, v2);
    } else {
    break;
    }
    }
    if (i == 0) break;
    }
    return pq.get_underline_container();
    }
    };