Duplikate in einem array finden

[Chris (Gast)]

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 ?

[SiMa (Gast)]

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

[Michael G. (linuxgeek)]

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 ;)

[Chris (Gast)]

Danke schon einmal für die Antworten.

Eine Sortierung ist nicht zwingend notwendig, nur interessant, wenn es 
Geschwindigkeitsvorteile beim auffinden von Duplikaten bringt.

[Chris (Gast)]

>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 
:)

[Jörg (Gast)]

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!)

[Professor (Gast)]

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?