Adding code to find first unused integer in set.

2 files changed, 15 insertions, 0 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 7659a7e..a2c5ff6 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -23,3 +23,6 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 
 \subsection{Treap (Cartesian Tree)}
 \lstinputlisting{datastructures/treap.cpp}
+
+\subsection{Erste unbenutzte natürliche Zahl}
+\lstinputlisting{datastructures/firstUnused.cpp}
diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp
new file mode 100644
index 0000000..141eb00
--- /dev/null
+++ b/datastructures/firstUnused.cpp
@@ -0,0 +1,12 @@
+// Erste natürliche Zahl nicht im set used.
+set<int> used;
+int unusedCounter = 1;
+
+int getFirstUnused() { // Laufzeit: O(log n) amortisiert.
+  auto it = used.lower_bound(unusedCounter);
+  while (it != used.end() && *it == unusedCounter) {
+    it++;
+    unusedCounter++;
+  }
+  return unusedCounter++; // Evtl. neuen Wert noch hinzufügen.
+}