查找列表中最低的未使用的唯一ID

假設有一個列表。列表中的每個項目都有一個唯一的ID。查找列表中最低的未使用的唯一ID

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

當我從這個列表中刪除一個項目時，該項目中的唯一標識符將與它一起使用。

List [5, 2, 3, 1]

現在說我想添加另一個項目的列表，並給它最低的唯一ID。

向列表中添加新項目時，獲取最低唯一標識的最簡單方法是什麼？

雖然這是限制：如果我在刪除項目時沒有重新分配另一個項目的唯一標識，我更喜歡它。

我意識到如果我在刪除4時重新分配了獨特的ID 5到唯一的ID 4，那麼我很容易找到唯一的ID。然後我可以得到列表的長度（5）並創建具有唯一性的新項目身份證號碼。

那麼還有另一種方式，那不涉及遍歷整個列表？

編輯：

語言是Java，但我想我在尋找一個通用的算法。

來源

2010-08-09 Brad

你在用什麼語言？另外：在這種情況下，使用'uniqueidentifier'標記可能不正確。你能看看是否有另一個標籤能更好地爲你服務？ – Tobiasopdenbrouw 2010-08-09 11:39:29

優先級隊列是一個偉大的數據結構，無論何時學習，都是一個很好的解決方案。不過，我想知道，如果只是一個簡單的列表將工作。爲什麼需要_lowest_而不是僅僅確保重用漏洞，是否有特定的原因？ – Dolphin 2010-08-09 14:09:20

一個簡單快捷的方法是將您的刪除的id放入優先級隊列中，當您插入新的id時（或者在隊列中使用第一個列表的size（）+ 1作爲id時，從那裏選擇下一個id是空的）。然而，這將需要另一個列表。

來源

2010-08-09 11:46:11 Avall

不錯的答案，歡迎來到堆棧溢出！通過「優先隊列」，你的意思是堆？ – Kobi 2010-08-09 11:52:24

謝謝！是堆或任何排序，允許找到O（1）中最低的ID。在Java中有一個PriorityQueue類。 – Avall 2010-08-09 11:57:53

它相當於一個搜索，只是這次你搜索一個缺失的數字。如果您的ID是排序整數，您可以從下往上開始檢查兩個ID之間的間隔是否爲1. 如果知道列表中有多少項目及其排序，則可以執行二分搜索。

來源

2010-08-09 11:43:43

我不認爲你可以做到這一點，而不需要遍歷列表。

當你說

「現在說我要到另一個項目添加到列表，並給它至少最高的唯一ID。 '

我假設你的意思是你想分配最低的可用ID，但沒有在別處使用過。

你可以這樣做：

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

這將返回最低自由指數。

這假定您的列表已排序，並且使用C＃，但您明白了。

來源

2010-08-09 11:44:17 Nobody

您可以維護一個可用ID的列表。

聲明一個布爾陣列（僞碼）：

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

當添加的元素，從寄存器的底部循環，直到一個false值被發現。將false值設置爲true，將該索引分配爲唯一標識符。

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

當您刪除元素時，只需將索引設置爲false即可。

您可以通過使用連續性標記來優化此列表，以便您不需要循環整個事物。

這對於索引沒有特定順序的示例最適合，因此您可以不必先排序。

來源

2010-08-09 11:46:15

將用於執行此操作的數據結構是僅允許唯一值的優先級二進制堆。

來源

2010-08-09 11:49:06

如何保持列表排序。而且你可以輕鬆地從一端移除它。

來源

2010-08-09 12:07:07 lalit

查找列表中最低的未使用的唯一ID

回答

相關問題