aboutsummaryrefslogtreecommitdiff
path: root/other/smallest_num_set.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/smallest_num_set.cpp')
-rw-r--r--other/smallest_num_set.cpp45
1 files changed, 45 insertions, 0 deletions
diff --git a/other/smallest_num_set.cpp b/other/smallest_num_set.cpp
new file mode 100644
index 0000000..f05147b
--- /dev/null
+++ b/other/smallest_num_set.cpp
@@ -0,0 +1,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);
+}