剑指offer（专项突破版）9.2 堆的应用
分析
如果能够找出k个最大的数字，那么第k大的数字就是这k个最大数字中最小的一个。由于每次都需要找出k个数字中的最小值，因此可以把这k个数字保存到最小堆中。每当从数据流中读出一个数字，就先判断这个新的数字是不是有必要添加到最小堆中。如果最小堆中元素的数目还小于k，那么直接将它添加到最小堆中。如果最小堆中已经有k个元素，那么将其和位于堆顶的最小值进行比较。如果新读出的数字小于或等于堆中的最小值，那么堆中的k个数字都比它大，因此它不可能是k个最大的数字中的一个。由于只需要保存最大的k个数字，因此新读出的数字可以忽略。如果新的数字大于堆顶的数字，那么堆顶的数字就是第k+1大的数字，可以将它从堆中删除，并将新的数字添加到堆中，这样堆中保存的仍然是到目前为止从数据流中读出的最大的k个数字，此时第k大的数字正好位于最小堆的堆顶。
使用STL自带的priority_queue：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> heap;
int size;
KthLargest(int k, vector<int>& nums) {
size = k;
for(int i = 0; i < nums.size(); i++){
add(nums[i]);
}
}
int add(int val) {
if(heap.size() < size){
heap.push(val);
}
else if(val > heap.top()){
heap.pop();
heap.push(val);
}
return heap.top();
}
};
|
分析
首先使用哈希表存储元素及其出现的次数，然后遍历每一个频次，建立最小堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
struct cmp{
bool operator() (const pair<int, int>& a, const pair<int, int>& b){
return a.second > b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
hash[nums[i]]++;
}
priority_queue<pair<int,int>, vector<pair<int, int>>, cmp> minHeap;
for( auto it = hash.begin(); it != hash.end(); it++){
if(minHeap.size() < k){
minHeap.push(*it);
}
else if(it->second > minHeap.top().second){
minHeap.pop();
minHeap.push(*it);
}
}
vector<int> res;
for(int i = 0; i < k; i++){
int cur = minHeap.top().first;
res.push_back(cur);
minHeap.pop();
}
return res;
}
};
|
- 时间复杂度：假设输入数组的长度为n。在大小为k的堆中进行添加或删除操作的时间复杂度是O（logk），因此上述代码的时间复杂度是O（nlogk）。
- 空间复杂度：上述代码需要一个大小为O（n）的哈希表，以及一个大小为O（k）的最小堆，因此总的空间复杂度是O（n）。
最大堆
这个题目要求找出和最小的k个数对。可以用最大堆来存储这k个和最小的数对。逐一将m×n个数对添加到最大堆中。当堆中的数对的数目小于k时，直接将数对添加到堆中。如果堆中已经有k个数对，那么先要比较待添加的数对之和及堆顶的数对之和（也是堆中最大的数对之和）。如果待添加的数对之和大于或等于堆顶的数对之和，那么堆中的k个数对之和都小于或等于待添加的数对之和，因此待添加的数对可以忽略。如果待添加的数对之和小于堆顶的数对之和，那么删除堆顶的数对，并将待添加的数对添加到堆中，这样可以确保堆中存储的是和最小的k个数对。每次都是将待添加的数对与堆中和最大的数对进行比较，而这也是用最大堆的原因。
接下来考虑如何优化。题目给出的条件是输入的两个数组都是递增排序的，这个特性我们还没有用到。如果从第1个数组中选出第k+1个数字和第2个数组中的某个数字组成数对p，那么该数对之和一定不是和最小的k个数对中的一个，这是因为第1个数组中的前k个数字和第2个数组中的同一个数字组成的k个数对之和都要小于数对p之和。因此，不管输入的数组nums1有多长，最多只需要考虑前k个数字。同理，不管输入的数组nums2有多长，最多也只需要考虑前k个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
struct cmp{
bool operator() (const pair<int,int>& a, const pair<int,int>& b){
return (long)(a.first + a.second) < (long)(b.first + b.second);
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> heap;
for(int i = 0; i < k && i < nums1.size(); i++){
for(int j = 0; j < k && j < nums2.size(); j++){
if(heap.size() < k){
heap.push(pair<int,int>(nums1[i],nums2[j]));
}
else if(nums1[i] + nums2[j] < heap.top().first + heap.top().second){
heap.pop();
heap.push(pair<int,int>(nums1[i],nums2[j]));
}
}
}
vector<vector<int>> res;
while(!heap.empty()){
auto it = heap.top();
vector<int> cur;
cur.push_back(it.first);
cur.push_back(it.second);
res.push_back(cur);
heap.pop();
}
return res;
}
};
|
- 时间复杂度：上述代码有两个相互嵌套的for循环，每个循环最多执行k次。在循环体内可能在最大堆中进行添加或删除操作，由于最大堆中最多包含k个元素，因此添加、删除操作的时间复杂都是$O(logk)$。这两个for循环的时间复杂度是$O(k^2logk)$。另外，上述代码还有一个while循环，它逐一从最大堆中删除元素并将对应的数对添加到链表中，这个while循环的时间复杂度是O(klogk)。因此，上述代码总的时间复杂度是$O(k^2logk)$。
- 空间复杂度：$O(k)$
最小堆
首先将nums1中的前k个元素与nums2的第一个元素组成的数对依次加入到堆中。这样做是为了初始化堆，确保堆中包含了每个nums1元素与nums2第一个元素组成的数对。然后进行循环处理，每次取出堆顶元素（当前和最小的数对），将其加入结果数组中，并将堆顶元素的索引往后移动一位，如果不超过nums2的范围，则将其加入堆中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
if (nums1.empty() || nums2.empty() || k <= 0) {
return {};
}
auto compare = [&](const pair<int,int>& a, const pair<int,int>& b) {
return (nums1[a.first] + nums2[a.second]) > (nums1[b.first] + nums2[b.second]);
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(compare)> heap(compare);
for(int i = 0; i < nums1.size() && i < k; i++){
heap.push({i, 0});
}
vector<vector<int>> res;
while(!heap.empty() && res.size() < k){
auto ids = heap.top();
heap.pop();
res.push_back({nums1[ids.first], nums2[ids.second]});
if(ids.second < nums2.size() - 1){
heap.push({ids.first, ids.second + 1});
}
}
return res;
}
};
|
decltype 是一个 C++ 关键字，用于获取某个表达式的类型。在这里，decltype(compare) 取得的类型就是 compare 这个 lambda 函数的类型。所以 decltype(compare)> 实际上是告诉编译器我们要使用 compare 这个类型的比较函数来对优先队列中的元素进行比较。
- 时间复杂度：上述代码先用一个for循环构建一个大小为k的最小堆，该循环的时间复杂度是O（klogk）。接下来是一个执行k次的while循环，每次对大小为k的最小堆进行添加或删除操作，因此这个while循环的时间复杂度也是O（klogk）。上述代码总的时间复杂度为O（klogk）。
- 空间复杂度：O(k)
总结
本章介绍了堆这种数据结构。堆又可以分成最大堆和最小堆。在最大堆中最大值总是位于堆顶，在最小堆中最小值总是位于堆顶。因此，在堆中只需要O（1）的时间就能得到堆中的最大值或最小值。
堆经常用来解决在数据集合中找出k个最大值或最小值相关的问题。通常用最大堆找出数据集合中的k个最小值，用最小堆找出数据集合中的k个最大值。
[!WARNING]
题目都是用priority_queue来做的，以后要补一下最大堆最小堆的具体实现。