Programmiere gerade einen ATmega8 in c und suche einer schnellstmöglichen Methode, in einem Array aus n Elementen die Duplikate los zu werden, d.h. das array soll letztendlich jeden Wert nur noch einmal enthalten. Kennt da jemand eine vorteilhaftere Methode als ein paar mal eine Schleife durchlaufen zu lassen? Ist bei vorherigem Sortieren der Werte der Gesamtaufwand eventuell kleiner ?
Wenn die Werte schon sortiert sind, musst Du natürlich nur einmal durchs Array. Wenn Du aber sortierst, kannst Du schon beim Sortieren die Duplikate rauswerfen
Mit nem schnellen Algorithmus sortieren und dann einmal durchlaufen und die Duplikate entfernen. Geht auch anders ist aber (aus dem Bauch raus) bestimmt langsamer. Ah da faellt mir ein: Modifizier den Algorithmus gleich so dass er keine Duplikate speichert, is noch schneller ;)
Danke schon einmal für die Antworten. Eine Sortierung ist nicht zwingend notwendig, nur interessant, wenn es Geschwindigkeitsvorteile beim auffinden von Duplikaten bringt.
>Ah da faellt mir ein: Modifizier den Algorithmus gleich so dass er keine >Duplikate speichert, is noch schneller ;) klatsch Logisch, das wäre eventuell auch eine eine Möglichkeit. Brett vorm Kopf :)
Falls Du keinen weiteren Speicherplatz zur Verfügung hast: Zwei Schleifen mit Indices i,j, i!=j: a(i)==a(j) => mehrfaches Vorkommen (hat aber O(n*n) Rechenaufwand, ist also nicht rechenoptimal, aber speicheroptimal!) sonst: "erzeuge" zweites Array B mit gleicher Anzahl Elemente wie Dein Array A, aber speichere in dieses die Indices von 0..n-1 Fasse nun die Elemente von Array A und B zusammen: (a,i), wobei a aus A, i aus B ist Definiere Grösser-Operator: (a1,i1) > (a2,i2) falls (a1 > a2) oder (a1 == a2 und i1 > i2) Sortiere nun die so zusammengefassten Elemente mittels Grösser-Operator Dann musst Du nur noch durch das Array laufen und testen, ob benachbarte Elemente (a1,i1),(a2,i2) mit a1==a2 existieren => mehrfaches Vorkommen!!! Falls Du die ursprüngliche Reihenfolge wieder herstellen möchtest: die steht im Array B in Form der Indices (hat O(n*log(n)) Rechenaufwand, ist also rechenoptimal, aber diesmal NICHT speicheroptimal!)
Mehr Input zu den Randbedingungen, bitte! - Welcher Wertebereich der Elemente im Array? - In-Place-Algorithmus? - Größenordnung des Arrays? - Zur Verfügung stehender Arbeitsspeicher während des Algorithmus?
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.