algorithm - 生成具有 O(1) 空间的唯一 ID？

Question

我们有一组对象，我们称它们为玩家。我们只能以随机顺序遍历这个组，例如没有Players[0]之类的东西.

每个玩家都有一个独特的 ID , 与 ID < len(Players) .玩家可以添加和删除到组中。当玩家被移除时，它将释放他的 ID ，如果添加了一个 Player，它将获得一个 ID。 .

如果我们想向 Players 添加一个新的 Player，我们必须生成一个新的唯一 ID .生成此类 ID 的最快方法是什么？在 O(1) 空间？

Answer 1

O(n log n) 使用二分查找是可能的。从 a = 0 和 b = n 开始。不变量是区间[a,b)中存在一个空闲id。重复以下直到 b - a = 1:令 m = a + floor((b - a)/2)，计算 [a, m) 和 [m, b) 中的 id 数。如果 [a, m) 少于 m - a id，则设置 b = m。否则，设 a = m。