Doppelt Elemente im Array zählen

[Gunnar Bittersmann]

Hello out there!

[…] wenn du das Array zuerst http://de.selfhtml.org/javascript/objekte/array.htm#sort@title=sortierst; Dann musst du in einer einfachen Schleife nur jeweils benachbarte Elemente vergleichen.

Aber wie stelle ich dann die urspüngliche Reihenfolge wieder her,

Vorher das Array kopieren: lineare Laufzeit O(n). Sortieren sollte in O(n · log n) möglich sein. Einfache Schleife zum Vergleichen jeweils benachbarter Elemente wieder O(n). Insgesamt also O(n · log n).

Der Algorithmus des OP hat eine doppelte Schleife, also O(n²), ist also zeitaufwändiger.

ohne mit diesem Mehraufwand die Ersparnis wieder zunichte zu machen?

Also von was für einem Mehraufwand sprichst du? ;-)

See ya up the road,
Gunnar