在列表中查找最小未使用的唯一id

Question

说有一个列表。列表中的每个项目都有一个唯一的id。

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

当我从这个列表中删除一个项目时，该项目的唯一标识符也会随之消失。

List [5, 2, 3, 1]

现在假设我想要添加另一个项目到列表中，并赋予它最小的唯一ID。

那么，在向列表中添加新项目时，获取最小唯一ID的最简单方法是什么？

这里有一个限制：如果删除一个项目时，最好不要重新分配另一个项目的唯一ID。

我意识到，如果我重新分配唯一ID 5 给唯一ID 4，然后我可以通过获取列表长度（5），并使用该数字创建具有唯一ID的新项目。

所以，还有另一种方法，不需要遍历整个列表吗？

编辑：

语言为Java，但我想找到一个通用算法。

- Brad

---

你使用的是哪种编程语言？此外，你在这种情况下使用 'uniqueidentifier' 标签可能是不正确的。你能否看看是否有另一个标签可以更好地为你服务？ - Tobiasopdenbrouw

一个优先队列是一个很好的数据结构，无论如何都值得学习，并且是解决问题的好方法。然而，我想知道是否只使用一个简单的列表就可以工作。你需要“最低”的特定原因吗？难道不只是确保重用空洞就可以了吗？ - Dolphin

Answer 1

一个简单快速的方法是将您删除的id放入优先级队列中，然后在插入新id时从队列中选择下一个id(或者当队列为空时使用第一个列表的size() + 1作为id)。但这需要另一个列表。

- Avall

---

很好的回答，欢迎来到Stack Overflow！你所说的“priority queue”，是指堆吗？ - Kobi

谢谢！是的，堆栈或任何已排序的东西，可以在O(1)时间内查找最低ID。在Java中，有一个类叫做PriorityQueue。 - Avall

Answer 2

你可以维护一个可用ID列表。

声明一个布尔数组（伪代码）：

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

当您添加一个元素时，从寄存器的底部开始循环，直到找到一个false值。将假值设置为真，并将该索引分配为唯一标识符。

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。

如果您有连续性标记，可以为更大的列表优化此过程，以便您不需要循环整个列表。

在您的示例中，这将最有效地工作，因为索引没有特定顺序，因此您可以跳过首先对它们进行排序的步骤。

- Tom Gullen

Answer 3

我认为你不能在不遍历列表的情况下完成这个任务。

当你说：

“现在假设我想要添加另一个项目到列表中，并给它最小的唯一ID。”

我理解你的意思是想要分配尚未被使用过的最低可用ID。

你可以这样做：

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

这将返回最低的空闲索引。

假设您的列表已排序，并且是使用C#编写的，但您可以理解其思想。

- Nobody

Answer 4

这相当于一次搜索，只不过这次你要搜索一个缺失的数字。如果你的ID是排序好的整数，你可以从底部开始检查两个ID之间的空格是否为1。 如果你知道列表中有多少项并且它已经排序好了，你可以实现二分搜索。

- Ido Weinstein

Answer 5

实现此操作所使用的数据结构是仅允许唯一值的优先级二叉堆。

- Bob Fincheimer

Answer 6

把列表保持有序，然后就可以轻松地从其中一端删除它。

- lalit