generische LinkedList nach Häufigkeit der Elemente füllen

[bradig]

Hi
ich habe ein kleines Problem.
Ich möchte eine generische LinkedList nach Häufigkeit der Elemente,die ich einfügen möchte füllen.
Bp: Bei 1, 1 , 4 , 2 , 1, 2 würde am Ende 1 , 2 ,4 ist die LinkedList stehen,da 1 (3 mal vorkommt),2(2 mal vorkommt) und 4 (nur 1 mal vorkommt).

wie man eine generische LinkedList implementiert weiß ich schon,aber Elemente nach Häufigkeit in die LinkedList einfügen weiß ich nicht.

Bitte un Hilfe

Herzlich

Bradig

 

[Kababär]

Hi,

einfach, aber eventuell nicht so elegant, wäre durch die Liste zu iterieren und in einer Hashmap als key den Wert des aktuell betrachteten Element einzutragen und als value die gezählten Häufigkeiten.
Danach eine LinkedList bauen aus den Keys der Hashmap abhängig von den gezählten Häufigkeiten.


Hashmap:
1 -> 3
2 -> 2
4 -> 1

Du könntest dir auch eine generische Klasse dafür bauen, aber eine Hashmap ist imho schneller. Auch wenn es eventuell nicht die schnellste Art ist.
Wobei es ja eigentlich auch reichen sollte, durch deine Anfangsliste zu iterieren und zuerst den Wert der größten Häufigkeit als erstes Element in eine neue Liste speicherst, den Wert mit der zweitgrößten Häufigkeit als zweites Element einträgst, etc.
Eine lokale Variable bspw count sollte die Häufigkeit zählen.
Im Prinzip wäre dies ein mal schneller, da du dir die Iterationen durch die Hashmap sparst.

 

[mrBrown]

Im Prinzip wäre dies ein mal schneller, da du dir die Iterationen durch die Hashmap sparst.

Dafür muss man n mal über die Liste iterieren, das müsste afaik langsamer sein, als n mal der HashMap hinzufügen und dann einmal über diese zu iterieren.

Ich möchte eine generische LinkedList nach Häufigkeit der Elemente,die ich einfügen möchte füllen.
Bp: Bei 1, 1 , 4 , 2 , 1, 2 würde am Ende 1 , 2 ,4 ist die LinkedList stehen,da 1 (3 mal vorkommt),2(2 mal vorkommt) und 4 (nur 1 mal vorkommt).

wie man eine generische LinkedList implementiert weiß ich schon,aber Elemente nach Häufigkeit in die LinkedList einfügen weiß ich nicht.

Sollen der Liste die Elemente schon sortiert hinzugefügt werden, oder soll die Liste selbst die Elemente sortieren, je nachdem wie oft sie hinzugefügt werden?

 

[bradig]

die Elemente sollen in der Liste nicht sortiert hinzugefügt werden.
bei 1 ,1,4,2,4,2,4,2,4 hätten wir zum Beispiel 4 ,2,1.

 

[mrBrown]

Du speicherst zu jedem ListenElement intern seinen Wert und seine Häufigkeit.
Wenn dann eins hinzugefügt wird, und es schon vorhanden ist, wird die Häufigkeit inkrementiert, und das Element nach vorne geschoben, wenn es jetzt häufiger ist als das (uU auch mehrere) daneben, damit es an der richtigen Stelle steht.
Wenn es nicht vorkommt wird es hinten an die Liste angehängt.

 

[Kababär]

Da gebe ich dir recht mrBrown.
Eine inkrementierug könnte man so bewerkstelligen:

map.put(key, map.get(key) + 1);

Positionen nach einer Änderung anpassen sollte mehr oder weniger trivial sein.

 

[mrBrown]

Da gebe ich dir recht mrBrown.
Eine inkrementierug könnte man so bewerkstelligen:

map.put(key, map.get(key) + 1);

Positionen nach einer Änderung anpassen sollte mehr oder weniger trivial sein.

map.compute(key, (k, v) -> ++v)

oder besser, dann hat man Neu hinzufügen mit drin:

map.merge(key, 1, (k, v) -> ++v)

Allerdings könnte man sich das leichter machen, indem man in den Nodes der LinkedList direkt die Häufigkeit speichert, dann spart man sich den Umweg über die Map