Priority Queue

tags: Hash Table,Heap (data structure),LeetCode101,Priority Queue,C++ Lambda class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> freq; // Note that: we need caputre a map by reference, // otherwise we can't use the operator[]. // See also: https://stackoverflow.com/a/6281071 auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b]; }; // Note that: here we need pass our lambda /comp_by_map/ to the // constructor of std::priority_queue....

tags: Priority Queue,LeetCode101 Using a min heap to keep k elements, top is the Kth largest element. class KthLargest { private: // min heap priority_queue<int, vector<int>, std::greater<int>> pq; int K; public: KthLargest(int k, vector<int>& nums) { K = k; for (auto n: nums) { add(n); } } int add(int val) { pq.push(val); while (pq.size() > K) { pq.pop(); } return pq.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

tags: Priority Queue,LeetCode101 Max heap priority queue class Solution { public: int findKthLargest(vector<int>& nums, int k) { // max heap priority_queue<int> pq; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { pq.push(*iter); } // The Kth largest element should let k > 1 not k > 0 for (; k > 1; --k) { pq.pop(); } return pq.top(); } };

tags: Priority Queue,LeetCode101 The key ideas: Use a std::pair to hold {count, index}, so it can compare count first then the index. Use a min heap priority queue to get the K weakest rows. class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { // min heap priority_queue< std::pair<int, int>, vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; for (auto iter = mat.begin(); iter != mat.end(); ++iter) { int c = count((*iter)....