2336. 无限集中的最小数字

🟠 🔖 设计 哈希表 有序集合 堆（优先队列） 🔗 力扣open in new window LeetCodeopen in new window

题目

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
int popSmallest() Removes and returns the smallest integer contained in the infinite set.
void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Example 1:

Input

["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]

[[], [2], [], [], [], [1], [], [], []]

Output

[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation

SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();

smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.

smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.

smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.

smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.

smallestInfiniteSet.addBack(1); // 1 is added back to the set.

smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and is the smallest number, and remove it from the set.

smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.

smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

Constraints:

1 <= num <= 1000
At most 1000 calls will be made in total to popSmallest and addBack.

题目大意

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类：

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。
int popSmallest() 移除并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不存在于无限集中，则将一个 num 添加到该无限集中。

示例：

输入

["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]

[[], [2], [], [], [], [1], [], [], []]

输出

[null, null, 1, 2, 3, null, 1, 4, 5]

解释

SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();

smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。

smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。

smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。

smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。

smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。

smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，且 1 是最小的整数，并将其从集合中移除。

smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。

smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

提示：

1 <= num <= 1000
最多调用 popSmallest 和 addBack 方法共计 1000 次

解题思路

维护最小堆：用最小堆保存被添加回集合的数字，保证堆顶始终是集合中的最小数，初始时最小堆为空。
追踪下一个自然数：用一个变量 current 表示当前自然数的上界，初始为 1，如果最小堆为空，最小的数字为 current。
使用集合去重：用一个集合 addBackSet 来存储被重新添加回集合的数字，方便查找，避免重复添加。
popSmallest：
- 如果 minHeap 非空，从堆中弹出堆顶元素作为结果，同时从 addBackSet 中移除。
- 如果 minHeap 为空，返回 current，并将 current 加 1。
addBack：
- 如果 num 小于 current 且不在 addBackSet 中，将其加入 minHeap 和 addBackSet。

复杂度分析

时间复杂度：O(log k)，
- popSmallest()：弹出最小堆的堆顶元素需要 O(log k)，其中 k 是当前堆的大小。如果最小堆为空时直接返回 current，时间复杂度为 O(1)。
- addBack(num)：插入堆需要 O(log k)，判断是否在集合中为 O(1)。
空间复杂度：O(k)，最小堆和集合的空间复杂度均为 O(k)，其中 k 是堆中元素的数量。

代码

var SmallestInfiniteSet = function () {
	this.minHeap = new MinHeap(); // 最小堆存储被添加回的数
	this.addBackSet = new Set(); // 存储被添加回的数，方便查找
	this.current = 1; // 当前自然数的下界
};

/**
 * @return {number}
 */
SmallestInfiniteSet.prototype.popSmallest = function () {
	if (this.minHeap.size() == 0) {
		return this.current++;
	}
	const res = this.minHeap.pop();
	this.addBackSet.delete(res);
	return res;
};

/**
 * @param {number} num
 * @return {void}
 */
SmallestInfiniteSet.prototype.addBack = function (num) {
	if (!this.addBackSet.has(num) && this.current > num) {
		this.minHeap.insert(num);
		this.addBackSet.add(num);
	}
};

// 最小堆
class MinHeap {
	constructor() {
		this.heap = [];
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0],
			last = this.heap.pop();
		if (this.heap.length > 0) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	size() {
		return this.heap.length;
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (left < this.heap.length && this.heap[left] < this.heap[min]) {
			min = left;
		}
		if (right < this.heap.length && this.heap[right] < this.heap[min]) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[i] < this.heap[parent]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * var obj = new SmallestInfiniteSet()
 * var param_1 = obj.popSmallest()
 * obj.addBack(num)
 */

2336. 无限集中的最小数字

# 2336. 无限集中的最小数字

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2336. 无限集中的最小数字

题目

题目大意

解题思路

复杂度分析

代码

相关题目