LeetCode：2336. 无限集中的最小数字（hash模拟 C++）

本文主要是介绍LeetCode：2336. 无限集中的最小数字（hash模拟 C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2336. 无限集中的最小数字

题目描述：

实现代码与解析：

set

原理思路：

优先级队列

2336. 无限集中的最小数字

题目描述：

现有一个包含所有正整数的集合 [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 次

实现代码与解析：

set

class SmallestInfiniteSet {
public:set<int> s;int m = 1; // 记录最小值SmallestInfiniteSet() {}int popSmallest() {int res = 0;if (s.empty()) {res = m++;} else {res = *s.begin();s.erase(s.begin());}return res;}void addBack(int num) {if (num < m) {s.insert(num);}}
};

class SmallestInfiniteSet {private TreeSet<Integer> set;private int m = 1;public SmallestInfiniteSet() {set = new TreeSet<Integer>();}public int popSmallest() {return set.isEmpty() ? m++ : set.pollFirst();}public void addBack(int num) {if (num < m) set.add(num);}
}

原理思路：

m 来表示在12345....序列中还没有pop出的最小值，set用来存放新add并且小于m的值，毕竟大于m的值已经存在且未pop出，在popSmallest函数中，若set为空，说明最小值为m，不为空，说明add的数有小于m的，返回set的第一个数。当然，很显然，这题用优先级队列也是可以写的。

不过要注意，优先级队列不能去重，添加的数可能已经存在与队列，所以要多一个数组来判断一下。

优先级队列

class SmallestInfiniteSet {
public:priority_queue<int, vector<int>, greater<int>> q;int m = 1; // 记录最小值vector<bool> d = vector<bool> (1010, false);SmallestInfiniteSet() {}int popSmallest() {int res = 0;if (q.empty()) {res = m++;} else {res = q.top();q.pop();d[res] = false;}return res;}void addBack(int num) {if (num < m && !d[num]) {q.push(num);d[num] = true;;}}
};

这篇关于LeetCode：2336. 无限集中的最小数字（hash模拟 C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！