diff options
| -rw-r--r-- | datastructures/datastructures.tex | 3 | ||||
| -rw-r--r-- | datastructures/firstUnused.cpp | 12 |
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. +} |