Duplikate in einem array finden

Gast #863509
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 ?
Gast #863515
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
Gast #863521
Danke schon einmal für die Antworten.

Eine Sortierung ist nicht zwingend notwendig, nur interessant, wenn es 
Geschwindigkeitsvorteile beim auffinden von Duplikaten bringt.
Gast #863523
>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 
:)
Gast #863529
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!)
Gast #863667
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?

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 18 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.