【LeetCode】Heap

[215] Kth Largest Element in an Array [Medium]

给个无序数组，返回第K大的数字。

方法1. 直接使用优先队列 priority_queue

 1 class Solution {
 2 public:
 3     int findKthLargest(vector<int>& nums, int k) {
 4         priority_queue<int> pq; // priority queue 实现一个大根堆
 5         for (int i = 0; i < nums.size(); ++i) {
 6             pq.emplace(nums[i]);
 7         }
 8         int i = 1;
 9         while(i++ < k) {
10             pq.pop();
11         }
12         return pq.top();
13     }
14 };

View Code

方法2. 自己实现堆排序（周末补上）

[373] Find K Pairs with Smallest Sums [Medium]

给两个有序数组，返回前k个和最小的组合对。

思路：用一个大根堆，放k个组合对，如果新来的小于当前的最大值，就把最大的踢出去。

 1 /* author: wyzhang
 2  * 2017/03/25
 3  * 最大堆
 4 */
 5 class Solution {
 6 public:
 7     struct cmp {
 8         bool operator()(pair<int, int> a, pair<int, int> b) {
 9             return a.first + a.second < b.first + b.second;
10         }
11     };
12     vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
13         priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
14         for (size_t i = 0; i < nums1.size() && i < k; ++i) {
15             for (size_t j = 0; j < nums2.size() && j < k; ++j) {
16                 if (pq.size() < k) {
17                     pq.push(make_pair(nums1[i], nums2[j]));
18                 } else {
19                     if (nums1[i] + nums2[j] < pq.top().first + pq.top().second) {
20                         pq.pop();
21                         pq.push(make_pair(nums1[i], nums2[j]));
22                     }
23                 } 
24             }
25         }
26         int i = min((size_t)k, pq.size());
27         vector<pair<int, int>> ans(i);
28         while(!pq.empty()) {
29             ans[i-1] = pq.top();
30             pq.pop();
31             i--;
32         }
33         return ans;
34     }
35 };

View Code