From 362b09086a49bed54182fc177908ba23c1757660 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 10 Jun 2017 23:47:37 +0200 Subject: Adding code to find first unused integer in set. --- datastructures/firstUnused.cpp | 12 ++++++++++++ 1 file changed, 12 insertions(+) create mode 100644 datastructures/firstUnused.cpp (limited to '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 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. +} -- cgit v1.2.3