priority_queue, partial_sort, nth_element

[sync-by-unito[bot]]

FB Questions: //953. Verifying an Alien Dictionary [Easy]

Classic:

partial_sort https://leetcode.com/problems/k-closest-points-to-origin/discuss/221532/C%2B%2B-STL-quickselect-priority_queue-and-multiset https://stackoverflow.com/questions/31195674/complexity-of-partial-sort-vs-nth-element/54227430#54227430

vector<vector<int>> kClosest(vector<vector<int>>& ps, int K) {
        partial_sort(ps.begin(), ps.begin()+K, ps.end(),[](vector<int>& p1, vector<int>& p2){ 
            return p1[0]*p1[0]+p1[1]*p1[1] < p2[0]*p2[0]+p2[1]*p2[1]; 
        });
        return vector<vector<int>> (ps.begin(), ps.begin()+K);
}

priority_queue custom comparator http://neutrofoton.github.io/blog/2016/12/29/c-plus-plus-priority-queue-with-comparator/ //973. K Closest Points to Origin [Med]

class Closest {
public:
    double dis; int x; int y;
    Closest(double d, int p_x, int p_y): dis(d), x(p_x), y(p_y){};
};
auto cmp = [](Closest a, Closest b){ return a.dis > b.dis; };
priority_queue<Closest, vector<Closest>, decltype(cmp)> q(cmp); (min heap)

Sorting vector: https://www.gormanalysis.com/blog/sorting-a-vector-in-cpp/

Iterator: https://www.techiedelight.com/iterate-over-characters-string-cpp/

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//23. Merge k sorted list [Hard]

class Solution_q23_a { // using priority queue (min heap), Time:O(kLogN), Space:O(k), // better than std:min_elements //https://leetcode.com/problems/merge-k-sorted-lists/discuss/10527/Difference-between-Priority-Queue-and-Heap-and-C%2B%2B-implementation public: ListNode mergeKLists(std::vector<ListNode> lists) { ListNode head = new ListNode(); ListNode current = head;

    //step1. push all lists' first item into priority queue; smaller to be on the top.
    auto cmp = [](ListNode* left, ListNode* right) { return (left->val) > (right->val); };
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> q(cmp);
    for (auto it = lists.cbegin(); it != lists.cend(); ++it) {
        if (*it) q.push(*it);
    }

    //step2. pop(add) the smallest to our list, add smallest->next to the priority queue. 
    while (!q.empty()) {
        ListNode* smallest = q.top();
        q.pop();
        current->next = smallest;
        current = current->next;

        if (smallest->next) {
            smallest = smallest->next;
            q.push(smallest);
        }
    }
    return head->next;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//973. K Closest Points to Origin [Med] //using partial_sort

class Solution { public: vector<vector> kClosest(vector<vector>& ps, int K) { partial_sort(ps.begin(), ps.begin()+K, ps.end(),[](vector& p1, vector& p2){ return p1[0]p1[0]+p1[1]p1[1] < p2[0]p2[0]+p2[1]p2[1]; });

    return vector<vector<int>> (ps.begin(), ps.begin()+K);
}

};//using priority_queue

class Closest {
public:
    double dis;
    int x;
    int y;
    Closest(double d, int p_x, int p_y): dis(d), x(p_x), y(p_y){};
};

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        auto cmp = [](Closest a, Closest b){ return a.dis > b.dis; };
        priority_queue<Closest, vector<Closest>, decltype(cmp)> q(cmp);

    for(auto &p: points){
        double d = sqrt(p[0]*p[0] + p[1]*p[1]);
        Closest c (d, p[0], p[1]);
        q.push(c);
    }

    vector<vector<int>> ret;
    for(int i=0; i<K; ++i){
        auto p = q.top(); q.pop();
        ret.push_back( vector<int>{p.x, p.y});
    }
    return ret;
}};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//692. Top K Frequent Words

class Words{ public: string str; int count; Words(string s, int c): str(s), count(c){}; };

class Solution { public: vector topKFrequent(vector& words, int k) { // Step 1. Build an map to store each word and their appearances count unordered_map<string, int> map; for(string &s : words){ map[s]++; }

    // Step 2. For the top K items, priority queue looks a good fit for the question
    // We need to store key-value like format into the priority queue.
    auto cmp = [](Words w1, Words w2){
        if(w1.count < w2.count)
            return true;
        else if(w1.count > w2.count)
            return false;
        else // if(w1.count == w2.count)
            return w1.str > w2.str;
    };
    priority_queue<Words, vector<Words>, decltype(cmp)> pq(cmp);
    for(auto &item : map)
        pq.push(Words(item.first, item.second));

    // Step 3. Pick k items
    vector<string> res;
    for(int i=0; i < k; i++){
        res.push_back((pq.top()).str);
        pq.pop();
    }         
    return res;
}

};