LeetCode + 《剑指Offer II》刷题笔记。
堆
如果面试题需要求出一个动态数据集合中的最大值或最小值，那么可以考虑使用堆来解决问题。最小堆经常用来求取数据集合中k个值最大的元素，而最大堆用来求取数据集合中k个值最小的元素。
优先队列C++
1
|
priority_queue<Type, Container, Functional>;
|
Type是要存放的数据类型
Container是实现底层堆的容器，必须是数组实现的容器，如vector、deque
Functional是比较方式/比较函数/优先级
此时默认的容器是vector，默认的比较方式是最大堆less<type>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
//最小堆
priority_queue <int,vector<int>,greater<int> > q;
//最大堆
priority_queue <int,vector<int>,less<int> >q;
//默认最大堆
priority_queue<int> a;
//pair
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty())
{
cout << a.top().first << ' ' << a.top().second << '\n';
a.pop();
}
//输出结果为：
2 5
1 3
1 2
|
常用函数
1
2
3
4
5
6
|
top()
pop()
push()
emplace()
empty()
size()
|
自定义比较方式
当数据类型并不是基本数据类型，而是自定义的数据类型时，就不能用greater或less的比较方式了，而是需要自定义比较方式。
在此假设数据类型是自定义的水果：
1
2
3
4
5
|
struct fruit
{
string name;
int price;
};
|
有两种自定义比较方式的方法，如下
1.重载运算符
重载”<”
-
若希望水果价格高为优先级高，则
1
2
3
4
5
6
7
8
9
10
|
//大顶堆
struct fruit
{
string name;
int price;
friend bool operator < (fruit f1,fruit f2)
{
return f1.peice < f2.price;
}
};
|
-
若希望水果价格低为优先级高
1
2
3
4
5
6
7
8
9
10
|
//小顶堆
struct fruit
{
string name;
int price;
friend bool operator < (fruit f1,fruit f2)
{
return f1.peice > f2.price; //此处是>
}
};
|
2.仿函数
若希望水果价格高为优先级高，则若希望水果价格高为优先级高，则
1
2
3
4
5
6
7
8
9
10
11
|
//大顶堆
struct myComparison
{
bool operator () (fruit f1,fruit f2)
{
return f1.price < f2.price;
}
};
//此时优先队列的定义应该如下
priority_queue<fruit,vector<fruit>,myComparison> q;
|
优先队列Java
Java提供了类型PriorityQueue实现数据结构堆。PriorityQueue在默认情况下是一个最小堆，如果使用最大堆调用构造函数就需要传入Comparator改变比较排序的规则。PriorityQueue实现了接口Queue。
值得强调的是，虽然Java中的PriorityQueue实现了Queue接口，但它并不是一个队列，也不是按照“先入先出”的顺序删除元素的。PriorityQueue是一个堆，每次调用函数remove或poll都将删除位于堆顶的元素。PriorityQueue根据比较规则的不同分为最大堆或最小堆。如果是最大堆，那么每次删除值最大的元素；如果是最小堆，那么每次删除值最小的元素。PriorityQueue的删除顺序与元素添加的顺序无关。
同理，PriorityQueue的函数element和peek都返回位于堆顶的元素，即根据堆的类型返回值最大或最小的元素，这与元素添加的顺序无关。
703 Kth Largest Element in a Stream
与数据流相关题目的特点是输入的数据是动态添加的，也就是说，可以不断地从数据流中读取新的数据，数据流的数据量是无限的。
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
|
class KthLargest {
private:
priority_queue<int,vector<int>,greater<int>> q;
int size;
public:
KthLargest(int k, vector<int>& nums) {
size=k;
for(int num:nums){
add(num);
}
}
int add(int val) {
q.push(val);
if(q.size()>size){
q.pop();
}
return q.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
|
347 Top K Frequent Elements
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
|
class Solution {
public:
struct myComparsion{
bool operator () (pair<int,int>& a,pair<int,int>& b){
return a.second>b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> numToCount;
for(int num:nums){
numToCount[num]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,myComparsion> q;
for(auto& it:numToCount){
q.push(it);
if(q.size()>k){
q.pop();
}
}
vector<int> res;
while(!q.empty()){
res.push_back(q.top().first);
q.pop();
}
return res;
}
};
|
373 Find K Pairs with Smallest Sums
最大堆
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer 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
|
class Solution {
public:
struct myComparsion{
bool operator()(const pair<int,int>& a,const pair<int,int>& b){
return a.first+a.second<b.first+b.second;
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<vector<int>> res;
priority_queue<pair<int,int>,vector<pair<int,int>>,myComparsion> q;
int m=nums1.size(),n=nums2.size();
for(int i=0;i<min(k,m);i++){
for(int j=0;j<min(k,n);j++){
q.emplace(nums1[i],nums2[j]);
if(q.size()>k){
q.pop();
}
}
}
while(!q.empty() && (k--)>0){
auto [a,b]=q.top();
res.push_back({a,b});
q.pop();
}
return res;
}
};
|
提交结果：Time Limit Exceeded
-
时间复杂度：O(k^2*log k)
两个相互嵌套的for循环，每个循环最多执行k次。在循环体内可能在最大堆中进行添加或删除操作，由于最大堆中最多包含k个元素，因此添加、删除操作的时间复杂都是O(log k)。这两个for循环的时间复杂度是O(k^2*log k)。另外还有一个while循环，它逐一从最大堆中删除元素并将对应的数对添加到结果中，这个while循环的时间复杂度是O(log k)。
因此，上述代码总的时间复杂度是O(k^2*log k)。
-
空间复杂度：O(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
|
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < min(k, m); i++) {
pq.emplace(i, 0);
}
while (k-- > 0 && !pq.empty()) {
auto [x, y] = pq.top();
pq.pop();
ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
if (y + 1 < n) {
pq.emplace(x, y + 1);
}
}
return ans;
}
};
|
-
时间复杂度：O(klog k)
-
空间复杂度：O(k)
Author
Anjana
LastMod
2022-07-08
License
原创文章，如需转载请注明作者和出处。谢谢！