Suche geeignete Datenstruktur

[blz]

Hi, ich hab hier ein kleines Problemchen:

Ich habe immer zwei zusammengehörige Zahlen, z.B.
1,7
7,11
7,13
13,25
32,35
11,12

Hier stellt sich schonmal die Frage, wie ich diese am besten speichere (abhängig von dem folgenden Problem).

Jetzt brauch ich einen effektiven Algorithmus, der das folgende macht:

Pseudocode Anfang:

Solange doppelte Werte existieren (egal ob an 1. oder 2. Stelle)
wenn ein häufigster Wert existiert, entferne ihn
sonst: wenn mehrere gleichhäufige werte existieren, entferne einen zufaelligen davon

Entferne nun solange je einen zufaelligen Wert, bis in jedem Tupel hoechstens noch ein Wert steht

Pseudocode Ende

Ich weiß nicht so recht, welche Datenstruktur hier die beste wäre, ich brauch das ganze möglichst effizient!
Hat jemand ne Idee?

 

[Joose]

Einfach eine Klasse erstellen mit zwei Attributen vom Typ int?

Die weiteren Anforderungen verstehe ich nicht genau. Ab wann ist ein Wert doppelt?
Aber es sollte doch reichen in einer Schleife die Häufigkeit usw. zu analysieren und in einer weiteren Schleife die zu entfernen, welche entfernt gehören

 

[blz]

ein Wert ist doppelt, sobald er mehr als einmal in irgendeinem Tupel auf irgendeiner Seite auftaucht.
In obigem Bsp. ist die 7 dreifach, die 13 und 11 jeweils zweifach vorhanden.

Was mich stoert, wenn ich mir selbst so eine Datenstruktur erstelle, ist, dass ich ja noch irgendwie eine weitere, am besten sortierte Datenstruktur brauche (welche?),
wo ich dann nochmal alle werte einfuegen muss

hier wollte ich eben nach dem elegantesten weg fragen!

 

[Joose]

Was mich stoert, wenn ich mir selbst so eine Datenstruktur erstelle, ist, dass ich ja noch irgendwie eine weitere, am besten sortierte Datenstruktur brauche (welche?),
wo ich dann nochmal alle werte einfuegen muss

Meiner Meinung nach reicht es vollkommen aus eine einfache Klasse zu erstellen um die beiden int werte zu halten.
Alle deine "Zahlenpärchen" kannst du in einer Liste halten und wenn du sie sortiert haben willst dann musst du dir eben überlegen wie du sie sortiert haben willst (SortedList?)
Eine zusätzliche Datenstruktur ist hierzu nicht notwendig.

 

[Dompteur]

Die Zahlenpaare kannst du in einer Liste (ArrayList) als ZahlenPaar (int w1, int w1) ablegen.
Wenn die Werte in einem "vernünftigen" Bereich liegen legst du ein Integer-Array (int anz[MAXVAL+1]) an.
Dann arbeitest du alle ZahlenPaare in einer Schleife ab:
anz[paarWert.w1]++
anz[paarWert.w2]++

LOOP:
Nun suchst du den höchsten anz[x]-Wert. Das Ergebnis ist jene Zahl, die am häufigsten vorkommt.
Mit dieser Zahl suchst du in der Liste nach einem Tupel, welches an einer der beiden Stellen die Zahl enthält.
Dieses Tupel entfernst du. Gleichzeitig verminderst du für die beiden Zahlen des Tupels die anz[x]-Werte.

Wenn die Abbruchbedingung noch nicht erfüllt ist, gehe zu LOOP

Wenn die Zahlen zu groß sind, kannst du statt eines Arrays eine HashMap verwenden.

 

[blz]

danke, habs hinbekommen