Sagen Sie, es gibt eine Liste. Jedes Element in der Liste hat eine eindeutige ID.
%Vor%Wenn ich ein Objekt aus dieser Liste entferne, gehört die eindeutige ID des Objekts dazu.
%Vor%Nun sage ich, dass ich ein weiteres Element zur Liste hinzufügen und ihm die niedrigste eindeutige ID geben möchte.
Was ist der einfachste Weg, die niedrigste eindeutige ID zu erhalten, wenn ein neues Element zur Liste hinzugefügt wird?
Hier ist jedoch die Einschränkung: Ich würde es vorziehen, wenn ich die eindeutige ID eines anderen Gegenstandes nicht beim Löschen eines Gegenstandes zuweisen würde.
Mir ist klar, dass es leicht wäre, die eindeutige ID zu finden, wenn ich der eindeutigen ID 4 eine eindeutige ID 5 zugewiesen hätte, wenn ich 4 gelöscht hätte. Dann könnte ich die Länge der Liste (5) ermitteln und das neue Element mit der eindeutigen ID erstellen mit dieser Nummer.
Gibt es also einen anderen Weg, der nicht die gesamte Liste durchläuft?
BEARBEITEN:
Sprache ist Java, aber ich denke, ich suche nach einem generischen Algorithmus.
Ein einfacher und schneller Weg ist, Ihre gelöschten IDs in eine Prioritätswarteschlange zu legen und die nächste ID von dort auszuwählen, wenn Sie neue einfügen (oder verwenden Sie size () + 1 der ersten Liste als ID, wenn die Warteschlange ist) leer). Dies würde jedoch eine andere Liste erfordern.
Sie könnten eine Liste der verfügbaren IDs verwalten.
Deklarieren Sie ein boolesches Array (Pseudocode):
%Vor% Wenn Sie ein Element hinzufügen, führen Sie eine Schleife vom unteren Rand des Registers aus, bis ein false -Wert gefunden wird. Setzen Sie den Wert false auf true und weisen Sie diesen Index als eindeutigen Bezeichner zu.
Wenn Sie ein Element entfernen, setzen Sie einfach den Index auf false.
Sie können dies für größere Listen optimieren, indem Sie Kontinuierlichkeitsmarker verwenden, so dass Sie das Ganze nicht mehr durchlaufen müssen.
Dies würde am besten für Ihr Beispiel funktionieren, wenn die Indizes in keiner bestimmten Reihenfolge sind, so dass Sie die Notwendigkeit, sie zuerst zu sortieren, überspringen.
Dies entspricht einer Suche, nur dieses Mal suchen Sie nach einer fehlenden Nummer. Wenn Ihre IDs ganze Zahlen sind, können Sie von unten nach oben gehen und prüfen, ob der Abstand zwischen zwei IDs 1 ist. Wenn Sie wissen, wie viele Elemente in der Liste und deren Sortierung enthalten sind, können Sie eine binäre Suche implementieren.
Ich denke nicht, dass Sie das tun können, ohne die Liste zu durchlaufen.
Wenn Sie sagen
'Jetzt sage ich, dass ich ein anderes Element hinzufügen möchte die Liste, und geben Sie es am wenigsten höchste eindeutige ID "
Ich nehme an, Sie meinen, dass Sie die niedrigste verfügbare ID zuweisen möchten, die an keiner anderen Stelle verwendet wurde.
Sie können dies tun:
%Vor%Dies gibt den niedrigsten freien Index zurück.
Dies setzt voraus, dass Ihre Liste sortiert ist und in C # ist, aber Sie bekommen die Idee.
Die Datenstruktur, die dafür verwendet wird, ist ein Priority Binary Heap, der nur eindeutige Werte zulässt.