Hi,
ich sitze gerade vor einem Algoproblem, welches man möglichst effizient in Java lösen soll. (Ich weiß nicht, ob ich hier richtig bin, vllt könnte man mich auch wo anders hin verweisen...)
Ich hab bis jetzt zwei Lösungsansätze bei denen ich zum einen nicht weiß, welcher effizienter ist und mir relativ sicher bin, dass das viel geschickter gehen müsste...
Also hier erstmal das Problem:
Man hat n verschiedene Elemente (sind in einem Object Array gespeichert) und diese soll man auf n/3 Buckets verteilen, wobei in jedes Bucket maximal 4 Elemente reinpassen. Deswetieren passen die Elemente in nur jeweils 2 Buckets rein.
Habt ihr eine Idee, wie man das möglichst effizient machen kann? Damti ihr seht, dass ich mir acuh schon Gedanken gemacht habe:
Ich habe mir überlegt, dass man ganz naiv immer ein Element nach dem anderen einfügen kann, wobei man immer den Bucket auffüllt, welcher noch nicht so viele Elemente besitzt. Sobald für ein Element beide zur Auswahl stehenden Buckets voll wären, schaut man sich im Prinzip wie bei der der Breitensuche die anderen Elemente in den Buckets an und verschiebt diese falls möglich in ein anderes Bucket, sodass das neue eingefügt werden kann. Das Ganze dürfte in O(n²) liegen.
Der andere Lösungsansaz wäre, dass man guckt, welche Buckets besonders beliebt sind und dann erst diejenigen auffüllt, welche überhaupt nicht gewollt werden. Das heißt, wenn in ein Bucket nur drei Elemente rein dürfen und da drinnen noch Platz für 4 ist, dann kommen die drei Elemente da sofort rein. Dürfte auch in O(n²) liegen.
Nur damit man einen Anhaltspunkt bekommt, wie groß das n ist: n ist eine beliebige ganze Zahl zwischen 2^15 und 2^25
Danke schon einmal Smile
