堆的应用

作者: 小墨 分类: LeetCode 发布时间: 2021-08-25 10:50 访问量:13,221
FavoriteLoading收藏

题目:给你一个整数数组 piles ,数组 下标从 0 开始 ,其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ,请你执行下述操作 恰好 k 次:

  • 选出任一石子堆 piles[i] ,并从中 移除 floor(piles[i] / 2) 颗石子。 注意:你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后,剩下石子的 最小 总数。floor(x) 为 小于 或 等于 x 的 最大 整数。(即,对 x 向下取整)

思路:每次选择列表中最大元素进行移除。

实现1:每次对最大的元素移除并更新后,重新对列表进行排序。

class Solution:
    import heapq
    def minStoneSum(self, piles: List[int], k: int) -> int:
        piles.sort()
        for i in range(k):
            piles[-1]-=int(piles[-1]/2)
            piles.sort()
        return sum(piles)

对时间复杂度进行分析:sort()方法的时间复杂度为O(NlogN),因此总的时间复杂度为KO(NlogN),会出现时间超时。

实现2:建立最大堆,每次只对第一个元素操作,并进行堆的弹出和插入。

class Solution(object):
    import heapq
    def minStoneSum(self, piles, k):
        total=sum(piles)
        piles=[-i for i in piles]
        heapq.heapify(piles)
        for i in range(k):
            max_value=-piles[0]
            total-=int(max_value/2)
            push_data=max_value-int(max_value/2)
            heapq.heappop(piles)
            heapq.heappush(piles,-push_data)
        return total

        """
        :type piles: List[int]
        :type k: int
        :rtype: int
        """

对时间复杂度进行分析:堆排序的插入时间复杂度为O(logN),因此总的时间复杂度为KO(logN),可以顺利通过。

     

如果觉得小墨的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论