无限集中的最小数字@ing

#leetcode #2024/09/18 #算法 #二叉堆 #优先级队列

目录

• 原题
• 思路
• 使用 python 描述
• 使用 JavaScript 描述

原题

思路

1. 初始化过程：
   • 设置 current 为 1，这是最小的正整数。
   • 创建一个空的 added_back 集合。
   • 创建一个空的 min_heap 最小堆。
2. popSmallest() 方法：
   • 首先检查 min_heap 是否为空。
   • 如果 min_heap 不为空：
     • 从 min_heap 中弹出最小值。
     • 从 added_back 集合中移除这个值。
     • 返回这个最小值。
   • 如果 min_heap 为空：
     • 返回当前的 current 值。
     • 将 current 增加 1。
3. addBack(num) 方法：
   • 检查 num 是否小于 current 且不在 added_back 集合中。
   • 如果条件满足：
     • 将 num 添加到 min_heap 中。
     • 将 num 添加到 added_back 集合中。
   • 如果条件不满足，不做任何操作。

SmallestInfiniteSet 类的工作原理：

• 它维护了一个动态的最小值（current），代表未被移除的最小正整数。
• 使用 min_heap 来高效地管理被添加回集合的较小数字。
• 使用 added_back 集合来快速检查一个数字是否已经被添加回集合。

使用 python 描述

# heapq  Python 标准库中的一个模块，用于实现堆队列算法，也称为优先队列算法
# heapq 默认实现的是最小堆
# heapq.heappush(heap, item)  将 item 的值加入 heap 中，保持堆的特性
# heapq.heappop(heap)  弹出并返回 heap 的最小的元素，保持堆的不变性
import heapq

class SmallestInfiniteSet:
    def __init__(self):
        # current 用于记录当前最小的数
        self.current = 1
        # added_back 用于记录已经添加回去的数
        self.added_back = set()
        # min_heap 二叉堆，用于存储当前最小的数
        self.min_heap = []

    def popSmallest(self) -> int:
        # 如果 min_heap 不为空，弹出最小的数
        if self.min_heap:
            smallest = heapq.heappop(self.min_heap)
            # 需要将弹出的数从 added_back 中删除
            self.added_back.remove(smallest)
            return smallest
        # 如果 min_heap 为空，返回当前最小的数，并将 current 加 1
        else:
            smallest = self.current
            self.current += 1
            return smallest

    def addBack(self, num: int) -> None:
        # 如果 num 小于当前最小的数，并且 num 没有被添加回去过，
        # 将 num 添加到 min_heap 中 ，并且把 num 放到集合added_back 中
        if num < self.current and num not in self.added_back:
            heapq.heappush(self.min_heap, num)
            self.added_back.add(num)

使用 JavaScript 描述