Mein Problem
Ich habe eine ArrayList mit fester Größe, die benutzerdefinierte Variablen enthält. Obwohl die ArrayList eine feste Größe hat, werden viele von ihnen tatsächlich null sein. Die Sache ist, dass ich die ArrayList ohne die Nullvariablen innerhalb es zurückgeben muss. Eine wichtige Anmerkung: In der ArrayList werden zuerst alle Nicht-Null-Elemente und dann alle darunter liegenden Nullen angezeigt, z. B. die Elemente nicht gemischt. Beispiel: [nicht null, nicht null, .... null, null, null]
Mein Workaround
Ich habe jedoch eine for-Schleife erstellt, die jedes Element innerhalb der ArrayList überprüft (vom letzten zum ersten Index), um festzustellen, ob es null ist oder nicht. Wenn null ist, würde ich diesen Code aufrufen:
%Vor%Meine Frage
Wenn die ArrayList zu groß ist, könnte diese Methode besonders langsam sein (oder nicht?). Ich habe mich gefragt, ob es eine bessere, leistungsfähigere Lösung gibt. AFAIK die .subList-Methode ist teuer.
Sie können eine Variante der binären Suche haben, wo Ihr benutzerdefinierter Vergleicher lautet:
Sie suchen nach dem ersten Nullelement.
Dies dauert O (logn) Zeit, wobei n die Größe des Arrays ist.
Wenn Sie jedoch die Unterliste von ArrayList verwenden, die keine NULL ist (vorausgesetzt, Sie werden sie in ein neues Listenobjekt kopieren), wird die lineare Zeit der kopierten Elemente sein, da Sie jede "berühren" müssen von ihnen.
Dies gibt Ihnen die gesamte Zeitkomplexität von O(logn + k) , wobei k die Anzahl der Nicht-Null-Elemente und n die Größe des Arrays ist.
Nach all Ihren ausstehenden Ratschlägen habe ich die ursprüngliche Methode so geändert, dass ich die letzte (erste) Nullposition nehmen und die .subList-Methode nur einmal aufrufen kann. Und hier ist es:
%Vor%Wenn Sie denken, dass es weiter modifiziert werden kann, um eine bessere Leistung zu ermöglichen, lassen Sie es uns wissen.
Tags und Links algorithm java time-complexity arraylist