vorletztes Element eines vector<T> ermitteln
-
Wie kann ich am elegantesten das vorletzte Element eines vector<T> ermitteln? Mit back() kriege ich ja das letzte.
-
ggggggggg schrieb:
Wie kann ich am elegantesten das vorletzte Element eines vector<T> ermitteln? Mit back() kriege ich ja das letzte.
Mir würden in den Sinn kommen
[v.size()-1] oder *(end()-2)
-
Beispielsweise *(v.end()-2) oder v[v.size() - 2] oder *(v.rbegin() + 1).
edit: Zu langsam
-
*(++vec.rbegin())
-
(&v.back())[-1]
-
-1[&v.back()]
-
v.end()[-1]
-
kkaw schrieb:
v.end()[-1]
äh ... -2 für das VORetzte.
-
Arcoth schrieb:
-1[&v.back()]
eher nicht.
-
std::vector<T>(original.begin(), original.end() - 1).back()
-
std::vector<int> v = ...; std::vector<int> idx(v.size()); std::iota(idx.begin(), idx.end(), 0); int n=1; for (int i=1; i<=v.size(); ++i) n*=i; int m = n - n/v.size()-1; while (m--) std::next_permutation(idx.begin(), idx.end()); std::cout << *std::next(v.begin(), idx.front()) << '\n';
-
auto index = vector.size(); while (index != vector.size() - 2) index = std::rand(); auto el = vector[index];
-
Nathan schrieb:
auto index = vector.size(); while (index != vector.size() - 2) index = std::rand(); auto el = vector[index];
Wie ist eigentlich die theoretische Laufzeitkomplexität hierbei?
-
Ich tippe auf O(1).
-
Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.
-
Arcoth schrieb:
Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.
wieso sollte worst case nicht ∞ sein? average case dürfte O(n) sein.
-
asfdlol schrieb:
Arcoth schrieb:
Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.
wieso sollte worst case nicht ∞ sein?
Ist das eine gültige Laufzeitkomplexität?
average case dürfte O(n) sein.
Das ist nicht möglich.
rand()
ist gleichmäßig verteilt, d.h. es macht keinen Unterschied welches N wir wählen, es wird im Durchschnitt die gleiche Anzahl Schritte benötigt.
-
Arcoth schrieb:
asfdlol schrieb:
Arcoth schrieb:
Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.
wieso sollte worst case nicht ∞ sein?
Ist das eine gültige Laufzeitkomplexität?
ob es eine gültige notation ist weiss ich nicht, jedoch liegt die lösung inhaltlich sehr nahe.
Arcoth schrieb:
average case dürfte O(n) sein.
Das ist nicht möglich.
rand()
ist gleichmäßig verteilt, d.h. es macht keinen Unterschied welches N wir wählen, es wird im Durchschnitt die gleiche Anzahl Schritte benötigt.ups, du hast recht. ich hab unsorgfältig gelesen dachte, dass die zufallszahl auf .size() begrenzt wird.
-
Die durchschnittliche Anzahl der Schleifendurchläufe ist RAND_MAX.
Zum Rest siehe http://en.wikipedia.org/wiki/Randomized_algorithm
-
Ich weise noch darauf hin, dass eine asymptotische Laufzeitkomplexität für den rand-Algorithmus unsinnig ist, da er nur für maximal RAND_MAX Einträge funktioniert. Für eine begrenzte Anzahl Eingaben ist jeder Algorithmus O(1). Falls da ::rand()%vector.size() stehen würde (was es sollte), wäre er O(n).