总结leetcode75中的堆/优先队列算法题解题思路。
上一篇:力扣75——图广度优先搜索
1 数组中的第K个最大元素
题目:
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
题解:
最大堆。
建立最大堆。然后依次取出k-1个,每取一个就重新修复最大堆。最后堆顶元素即为所求值。
class Solution {
public:
void maxHeapify(vector<int>& a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a[i], a[largest]);
maxHeapify(a, largest, heapSize);
}
}
void buildMaxHeap(vector<int>& a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
swap(nums[0], nums[i]);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
};
2 无限集中的最小数字
题目:
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类:
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
int popSmallest() 移除 并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不 存在于无限集中,则将一个 num 添加
到该无限集中。
题解:
用set类型的s记录被删除的变量。用minV记录最小值。
如果采用最小堆,可以将1~1000的数据存入最小堆或优先级队列,然后实现删除插入。
class SmallestInfiniteSet {
public:
int minV = 1;
set<int> s;
SmallestInfiniteSet() {
}
int popSmallest() {
int res = minV;
s.insert(minV);
while (s.count(++minV)) {}
return res;
}
void addBack(int num) {
if (s.count(num)) s.erase(num);
minV = min(minV, num);
}
};
3 最大子序列的分数
题目:
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,两者长度都是 n ,再给你一个正整数
k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。
对于选择的下标 i0 ,i1 ,..., ik - 1 ,你的 分数 定义如下:
nums1 中下标对应元素求和,乘以 nums2 中下标对应元素的 最小值 。
用公示表示:
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
请你返回 最大 可能的分数。
一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合,
也可以不删除任何元素。
题解:
最小堆。
对于nums2中的任意一个数nums2[i],如果它是k个数的最小值,则另外的k-1个数都应该比它大。所以,先对nums2进行降序排序,然后从第k大的数开始枚举。每次从现有数据中去除nums1[j]最小的那个,然后加入当前枚举到的值nums1[i],计算得分。
做法:先对nums2进行降序排序,然后按顺序取nums1中的k个数,nums2[k-1]为nums2的k个数的最小值。遍历时:从k个nums1数中pop掉最小的那个,然后加入nums1[i],重新计算分数。
nums1的pop过程可以用最小堆(优先级队列)来实现。
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
// 根据nums2的值排序,拿到一个降序的索引
vector<int> ids(nums2.size());
iota(ids.begin(), ids.end(), 0);
sort(ids.begin(), ids.end(), [&](const int& i, const int& j) { return nums2[i] > nums2[j]; });
// 使用优先队列,最小值权重最高
priority_queue<int, vector<int>, greater<int>> pq;
long long res = 0, sumV = 0;
for (int i = 0; i < k; ++i) {
pq.emplace(nums1[ids[i]]);
sumV += nums1[ids[i]];
}
res = sumV * nums2[ids[k - 1]];
for (int i = k; i < ids.size(); ++i) {
if (nums1[ids[i]] > pq.top()) {
// 无论 res需不需要更新,最小值都需要更新
sumV += nums1[ids[i]] - pq.top();
res = max(res, sumV * nums2[ids[i]]);
pq.pop();
pq.emplace(nums1[ids[i]]);
}
}
return res;
}
};
4 雇佣 K 位工人的总代价
题目:
给你一个下标从 0 开始的整数数组 costs ,其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人:
总共进行 k 轮雇佣,且每一轮恰好雇佣一位工人。
在每一轮雇佣中,从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人,
如果有多位代价相同且最小的工人,选择下标更小的一位工人。
比方说,costs = [3,2,7,7,1,2] 且 candidates = 2 ,第一轮雇佣中,我们选择第 4 位工
人,因为他的代价最小 [3,2,7,7,1,2] 。
第二轮雇佣,我们选择第 1 位工人,因为他们的代价与第 4 位工人一样都是最小代价,而且下标
更小,[3,2,7,7,2] 。注意每一轮雇佣后,剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人,那么下一轮雇佣他们中代价最小的一人,如果有多位代价
相同且最小的工人,选择下标更小的一位工人。
一位工人只能被选择一次。
返回雇佣恰好 k 位工人的总代价
题解:
优先级队列。
2个优先级队列,最小值权重最高,分别存储前candidates个和后candidates个costs。
每次判断哪个队列的队头值更小,则雇佣对应的工人,然后弹出队列。文章来源:https://www.toymoban.com/news/detail-653407.html
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
long long ans = 0;
int left = 0, right = costs.size() - 1;
priority_queue<int, vector<int>, greater<int>> prePq, purPq;
while (k--) {
while (prePq.size() < candidates && left <= right) {
prePq.emplace(costs[left++]);
}
while (purPq.size() < candidates && left <= right) {
purPq.emplace(costs[right--]);
}
int a = prePq.empty() ? INT_MAX : prePq.top();
int b = purPq.empty() ? INT_MAX : purPq.top();
if (a <= b) {
ans += a;
prePq.pop();
} else {
ans += b;
purPq.pop();
}
}
return ans;
}
};
1-4 解题总结
特点:数据有优先级。最大、最小、第k大、第k小。
工具:自己建立最大堆或最小堆、使用优先级队列priority_queue。文章来源地址https://www.toymoban.com/news/detail-653407.html
到了这里,关于力扣75——堆/优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!