diff options
Diffstat (limited to 'datastructures/firstUnused.cpp')
| -rw-r--r-- | datastructures/firstUnused.cpp | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp new file mode 100644 index 0000000..16b0c21 --- /dev/null +++ b/datastructures/firstUnused.cpp @@ -0,0 +1,13 @@ +// Erste natürliche Zahl nicht im set used. +set<int> used; +int unusedCounter = 1; + +int get_first_unused() { // Laufzeit: O(log n) amortisiert. + auto it = used.lower_bound(unusedCounter); + while (it != used.end() && *it == unusedCounter) { + it++; + unusedCounter++; + } + used.insert(unusedCounter); + return unusedCounter++; +} |