aboutsummaryrefslogtreecommitdiff
path: root/smallest_num_set.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /smallest_num_set.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'smallest_num_set.c')
-rw-r--r--smallest_num_set.c100
1 files changed, 100 insertions, 0 deletions
diff --git a/smallest_num_set.c b/smallest_num_set.c
new file mode 100644
index 0000000..dabe17e
--- /dev/null
+++ b/smallest_num_set.c
@@ -0,0 +1,100 @@
+// 2336. Smallest Number in Infinite Set
+#include <stdbool.h>
+#include <stdlib.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
+ */
+
+typedef struct {
+ int *heap;
+ bool *hash;
+ int heap_size;
+} SmallestInfiniteSet;
+
+SmallestInfiniteSet *SmallestInfiniteSetCreate() {
+ SmallestInfiniteSet *res = malloc(sizeof(SmallestInfiniteSet));
+ res->heap = malloc(1001 * sizeof(int));
+ res->hash = malloc(1000 * sizeof(bool));
+ for (int i = 0; i < 1000; i++) {
+ res->heap[i] = i + 1;
+ res->hash[i] = true;
+ }
+ res->heap_size = 1000;
+ return res;
+}
+
+int SmallestInfiniteSetPopSmallest(SmallestInfiniteSet *obj) {
+ if (!obj->heap_size)
+ return -1;
+ int res = obj->heap[0];
+ obj->hash[res - 1] = false;
+ obj->heap[0] = obj->heap[obj->heap_size - 1];
+ obj->heap_size--;
+ int pos = 0, tmp;
+ while (pos < obj->heap_size) {
+ if ((2 * pos + 1) >= obj->heap_size)
+ break;
+ if (2 * pos + 1 == obj->heap_size - 1) {
+ if (obj->heap[pos] > obj->heap[2 * pos + 1]) {
+ tmp = obj->heap[pos];
+ obj->heap[pos] = obj->heap[2 * pos + 1];
+ obj->heap[2 * pos + 1] = tmp;
+ pos = 2 * pos + 1;
+ }
+ break;
+ }
+ if (obj->heap[pos] > obj->heap[2 * pos + 1] ||
+ obj->heap[pos] > obj->heap[2 * pos + 1]) {
+ if (obj->heap[2 * pos + 1] <= obj->heap[2 * pos + 1]) {
+ tmp = obj->heap[2 * pos + 1];
+ obj->heap[2 * pos + 1] = obj->heap[pos];
+ obj->heap[pos] = tmp;
+ pos = 2 * pos + 1;
+ } else {
+ tmp = obj->heap[2 * pos + 2];
+ obj->heap[2 * pos + 2] = obj->heap[pos];
+ obj->heap[pos] = tmp;
+ pos = 2 * pos + 2;
+ }
+ } else
+ break;
+ }
+ return res;
+}
+
+void SmallestInfiniteSetAddBack(SmallestInfiniteSet *obj, int num) {
+ if (obj->hash[num - 1])
+ return;
+ else
+ obj->hash[num - 1] = true;
+ obj->heap[obj->heap_size] = num;
+ int pos = obj->heap_size;
+ obj->heap_size++;
+ int tmp;
+ while (pos && (obj->heap[pos] < obj->heap[(pos - 1) / 2])) {
+ tmp = obj->heap[(pos - 1) / 2];
+ obj->heap[(pos - 1) / 2] = obj->heap[pos];
+ obj->heap[pos] = tmp;
+ pos = (pos - 1) / 2;
+ }
+}
+
+void SmallestInfiniteSetFree(SmallestInfiniteSet *obj) {
+ free(obj->heap);
+ free(obj);
+}
+
+int main() {
+ SmallestInfiniteSet *obj = SmallestInfiniteSetCreate();
+ int param_1 = SmallestInfiniteSetPopSmallest(obj);
+ SmallestInfiniteSetAddBack(obj, 2);
+ SmallestInfiniteSetFree(obj);
+}