Znajdowanie najniższego nieużywanego unikalnego identyfikatora na liście

Question

Powiedz, że istnieje lista. Każda pozycja na liście ma unikalny identyfikator.

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

Kiedy usuwam przedmiot z tej listy, id z nim związany jest unikalny identyfikator.

List [5, 2, 3, 1] 

teraz, że chcę, aby dodać kolejną pozycję do listy, i nadać mu najmniejszą najniższą unikalny identyfikator.

Jaki jest najłatwiejszy sposób uzyskania najniższego unikalnego identyfikatora podczas dodawania nowego elementu do listy?

Oto jednak ograniczenie: wolałbym, aby podczas przypisywania elementu nie przypisać unikatowego id innego przedmiotu.

Zdaję sobie sprawę, że łatwo byłoby znaleźć unikalny identyfikator, jeśli przypisałbym unikalny identyfikator 5 do unikalnego identyfikatora 4, gdy usunąłem 4. Wtedy mógłbym uzyskać długość listy (5) i utworzyć nowy element z unikalnym id z tym numerem.

Czy istnieje inny sposób, który nie wymaga powtarzania całej listy?

EDIT:

Język jest Java, ale przypuszczam, że szukam algorytmu ogólnej.

Answer 1

Łatwym szybkim sposobem jest po prostu umieszczenie usuniętych identyfikatorów w kolejce priorytetowej, a następnie wybranie następnego identyfikatora podczas wstawiania nowych (lub użycie size() + 1 z pierwszej listy jako id, gdy kolejka jest pusty). Wymagałoby to jednak innej listy.

Answer 2

Jest to odpowiednik wyszukiwania, tym razem szukany jest brakujący numer. Jeśli twoje identyfikatory są posortowane liczbami całkowitymi, możesz zacząć od dołu do góry, sprawdzając, czy odstęp między dwoma identyfikatorami wynosi 1. Jeśli wiesz, ile pozycji na liście i posortowanych, możesz zaimplementować wyszukiwanie binarne.

Answer 3

Nie sądzę, że można to zrobić bez powtarzania listy.

Kiedy mówisz

„Teraz mówią, że chcą, aby dodać kolejny element do listę, i nadać mu najmniejszą najwyższy unikalny identyfikator. "

Zakładam, że masz na myśli, że chcesz przypisać najniższy dostępny identyfikator, który nie był używany w innym miejscu.

Można to zrobić:

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

ten zwraca najniższy wolny indeks.

Zakłada, że ​​twoja lista jest posortowana i znajduje się w C#, ale masz pomysł.

Answer 4

Możesz zachować listę dostępnych identyfikatorów.

stwierdzenie tablicę logiczną (pseudo kodu):

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

Podczas dodawania pierwiastka pętli od dna aż do rejestru wartość false znajduje. Ustaw wartość false na true, przypisz ten indeks jako unikalny identyfikator.

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; 
} 

Po usunięciu elementu ustaw indeks na wartość false.

Możesz to zoptymalizować dla większych list dzięki znacznikom ciągłości, dzięki czemu nie musisz zapętlać całej rzeczy.

Najlepiej sprawdzi się w tym przykładzie, gdy indeksy nie są w określonej kolejności, więc pomijasz konieczność posortowania ich w pierwszej kolejności.

Answer 5

Struktura danych, która byłaby użyta w tym celu, jest priorytetowym stosem binarnym, które zezwala na unikalne wartości.

Answer 6

Jak zachować listę posortowaną. i możesz łatwo usunąć go z jednego końca.