在手机上如何制作网站,建筑工程信息网站,wordpress是什么框架,小程序app公众号的区别贪心优先队列
请看答案需求#xff1a;得到最大分数。易猜到#xff0c;得到最大分数的取法是每次取数组中最大的数字(贪心思路)。
问题转化为#xff1a;如何快速找到数组中最大的数字#xff0c;根据问题规模 k 1 0 5 k10^5 k105#xff0c;维护优先队列即可 O ( k l…贪心优先队列
请看答案需求得到最大分数。易猜到得到最大分数的取法是每次取数组中最大的数字(贪心思路)。
问题转化为如何快速找到数组中最大的数字根据问题规模 k 1 0 5 k10^5 k105维护优先队列即可 O ( k l o g 2 n ) O(klog_2n) O(klog2n)解决问题。
请看如下代码
class Solution {
public:long long maxKelements(vectorint nums, int k) {// priority_queueint pq(nums.begin(), nums.end());priority_queueint pq(lessint(), move(nums));long long ans 0;while (k --) {int t pq.top();pq.pop();ans t;t (t 2) / 3;pq.push(t);}return ans;}
};时间复杂度 O ( n k l o g n ) O(nklogn) O(nklogn)维护优先队列的时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( 1 ) O(1) O(1)只使用常数级空间。
致语
理解思路很重要。请读者放心留言可以是疑惑的点或者讨论墨染看到会回复的。
