blob: f05147b83a4707fd75c76f8524e284a57edce1e9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
// 2336. Smallest Number in Infinite Set
#include "leetcode.h"
/*
* you have a set which contains all positive integers [1,2,3,...]
* implement the SmallestInfiniteSet class:
* - SmallestInfiniteSet() initialises 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
*/
class SmallestInfiniteSet {
public:
int k = 1;
unordered_map<int, int> um;
SmallestInfiniteSet() {
for (int i = 1; i <= 1000; i++)
um[i] = i;
}
int popSmallest() {
int d = um[k];
um.erase(k);
for (int i = k + 1; i <= 1000; i++) {
if (um.find(i) != um.end()) {
k = i;
break;
}
}
return d;
}
void addBack(int num) {
um[num] = num;
if (num < k)
k = num;
}
};
int main() {
SmallestInfiniteSet *obj = new SmallestInfiniteSet();
int param_1 = obj->popSmallest();
obj->addBack(2);
}
|