【每日一题】从数量最多的堆取走礼物-CSDN博客

Tag

【优先队列】【排序】【数组】【2023-10-28】

---

题目来源

2558. 从数量最多的堆取走礼物
​

---

题目解读

执行 k 次操作每次从数量最多的堆中取走礼物。

---

解题思路

每次要从礼物数量最多的堆中取走一定的礼物在没学过 优先队列 这种数据结构之前可以使用 排序 来完成每次都从礼物数量最多的堆中取走一定的礼物。

方法一将会介绍排序的方方法二介绍优先队列的方法。

方法一排序

先对礼物数组进行升序排序数组中最后一个元素就是最大的礼物数将其值更新为平方根值。对以上操作执行 k 次最后数组中所有礼物数量之和就是我们要返回的答案。

实现代码

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        int n = gifts.size();
        while (k--) {
            sort(gifts.begin(), gifts.end());
            gifts[n-1] = sqrt(gifts[n-1]);
        }
        long long res = accumulate(gifts.begin(), gifts.end(), 0ll);
        return res;
    }
};

复杂度分析

时间复杂度$O(k\cdot nlogn)$$k$ 为执行的时间$n$ 为数组 gifts 的长度。

空间复杂度$O(nlogn)$。

方法二优先队列

我们使用大顶堆来维护各堆中礼物的数量进行 k 次如下的操作每次从左取出最大的一个求平方根之后将结果放入堆中。最后大顶堆中所有礼物数量之和就是我们要返回的答案。

实现代码

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> pq(gifts.begin(), gifts.end());
        while (k--) {
            int maxGift = pq.top();
            pq.pop();
            pq.push(sqrt(maxGift));
        }

        long long res = 0;
        while (!pq.empty()) {
            res += pq.top();
            pq.pop();
        }
        return res;
    }
};

复杂度分析

时间复杂度$O(nlogn)$$n$ 为数组 gifts 的长度。

空间复杂度$O(logn)$。

---

其他语言

python3

这里只给出 python3 的示例代码。

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        pq = [-gift for gift in gifts]
        heapify(pq)
        while k:
            x = heappop(pq)
            heappush(pq, -int(sqrt(-x)))
            k -= 1
        return -sum(pq)

在 python3 中我们引入 heap 模块来构建优先队列通过 heapify 构建最小堆因为我们希望使用最大堆所以将礼物数量取负数放入堆中。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。

如果大家有更优的时间、空间复杂度方法欢迎评论区交流。

最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。