ARTS Week 28, 2024

2024-07-13 约 291 字预计阅读 1 分钟

1.Algorithm

方法一：排序

class Solution:
    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:
        stock = sorted(stock)
        return(stock[:cnt])

对原数组从小到大排序后取出前 cnt 个数即可。

方法二：堆

我们用一个大根堆实时维护数组的前 cnt 小值。首先将前 cnt 个数插入大根堆中，随后从第 cnt+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。Python 语言中的堆为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 cnt 小值。

class Solution:
    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:
        if cnt == 0:
            return list()

        hp = [-x for x in stock[:cnt]]
        heapq.heapify(hp)
        for i in range(cnt, len(stock)):
            if -hp[0] > stock[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -stock[i])
        ans = [-x for x in hp]
        return ans

2.Review

Shooting conspiracies trend on X as Musk endorses Trump

可能改变历史的一枪

3.Tip

CF-Workers-docker

通过Cloudflare Worker搭建免费的docker hub加速器

目录