Suchen der niedrigsten unbenutzten eindeutigen ID in einer Liste

Question

Sagen wir, es gibt eine Liste. Jedes Element in der Liste hat eine eindeutige ID.

List [5, 2, 4, 3, 1] 

Wenn ich einen Artikel aus dieser Liste entferne, gehört die eindeutige ID aus dem Artikel dazu.

List [5, 2, 3, 1] 

Jetzt sagen, ich möchte ein anderes Element zur Liste hinzufügen, und geben Sie es die niedrigste eindeutige ID.

Was ist der einfachste Weg, um die niedrigste eindeutige ID zu erhalten, wenn ein neues Element zur Liste hinzugefügt wird?

Hier ist die Einschränkung: Ich würde es vorziehen, wenn ich nicht die eindeutige ID eines anderen Artikels beim Löschen eines Artikels neu zuweisen würde.

Ich weiß, es wäre einfach, die eindeutige ID zu finden, wenn ich eindeutige ID 5 an eindeutige ID 4 zugewiesen, wenn ich gelöscht 4. Dann könnte ich die Länge der Liste (5) und das neue Element mit dem einzigartigen erstellen ID mit dieser Nummer.

Gibt es einen anderen Weg, der nicht die gesamte Liste durchläuft?

EDIT:

Sprache ist Java, aber ich nehme an, ich bin für einen generischen Algorithmus suchen.

Answer 1

Ein einfacher 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.

Answer 2

Das 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.

Answer 3

Ich glaube nicht, dass Sie dies tun können, ohne die Liste zu durchlaufen.

Wenn Sie

sagen: ‚Nun sage ich ein anderes Element zu der Liste hinzugefügt werden soll, 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 woanders nicht verwendet wurde.

Sie können dies tun:

private int GetLowestFreeID(List list){ 
    for (int idx = 0; idx < list.Length; ++i){ 
     if (list[idx] == idx) continue; 
     else return idx; 
    } 
} 

dies gibt den niedrigste freien Index.

Dies geht davon aus, dass Ihre Liste sortiert ist, und in C# ist, aber Sie bekommen die Idee.

Answer 4

Sie können eine Liste der verfügbaren IDs verwalten.

Deklarieren einen booleschen Array (Pseudocode):

boolean register[3]; 
register[0] = false; 
register[1] = false; 
register[2] = false; 

Wenn Sie ein Element gefunden, Schleife von der Unterseite des Registers, bis ein false Wert hinzufügen. Setzen Sie den Wert false auf true und weisen Sie diesen Index als eindeutigen Bezeichner zu.

removeObject(index) 
{ 
    register[index] = false; 
} 

getsetLowestIndex() 
{ 
    for(i=0; i<register.size;i++) 
    { 
     if(register[i]==false) 
     { 
      register[i] = true; 
      return i; 
     } 
    } 

    // Array is full, increment register size 
    register.size = register.size + 1; 
    register[register.size] = true; 
    return register.size; 
} 

Wenn Sie ein Element entfernen, setzen Sie den Index einfach auf false.

Sie können dies für größere Listen optimieren, indem Sie Konti- nitätsmarker verwenden, sodass Sie nicht die gesamte Schleife durchlaufen müssen.

Dies würde am besten für Ihr Beispiel funktionieren, wo die Indizes in keiner bestimmten Reihenfolge sind, so dass Sie die Notwendigkeit, sie zuerst zu sortieren, überspringen.

Answer 5

Die Datenstruktur, die dazu verwendet werden soll, ist ein Priority Binary Heap, der nur eindeutige Werte zulässt.

Answer 6

Wie wäre es, die Liste sortiert zu halten? und dann können Sie es leicht von einem Ende entfernen.