我需要创建一个支持以下操作的整数数据结构 -
- 在给定位置插入项目(添加项目位置)
- 从给定位置删除项目(删除位置)
- 随机选择任意给定位置(Selectposition)
- 随机洗牌项目。
我需要保持一颗清醒的头脑。用()表示。有关更多详细信息，请参阅示例。
Ex-
lets say my initial state is
(1) 2 3 4 5
Where () represents my current head
After Add 6 2
state - (1) 6 2 3 4 5
After Delete 5
state - (1) 6 2 3 5
After Select 3
state - 1 6 (2) 3 5
After shuffle
state - 5 (2) 6 1 3
shuffle will shuffle all the items randomly. But will preserve the head.
最佳答案
创建每个大小为 2k 的 bin，并拥有 n/k 个(因此分配的空间总数为 2n)。
- 每个“bin”都会知道其起始索引和结束索引。
- 插入时，首先找到相关的bin。如果使用线性搜索，这需要 O(n/k) 时间。将元素添加到容器中(假设暂时未满)，并将该特定容器中的所有元素向右移动。然后，更新您刚刚修改的 bin 之后的所有 bin。这将需要
O(n/k + k)时间。 - 删除与添加类似，在
O(n/k + k)中再次完成。时间。 - 选择:查找相关垃圾箱(同样，线性搜索将为您提供
O(n/k)，并且该项目在其中的位置可以在O(1)中找到)。但请注意，您可以使用二分搜索在O(log(n/k))中找到该 bin。时间，所以选择是O(log(n/k)). - 使用 fisher yates 进行随机播放在
O(n).
此外，当 bin 已满时，只需重新分配整个数组，并在需要时增加 bin 大小。这个操作是O(n) ，并且至少在 O(k) 之后完成插入，所以当谈论摊销时间时它仍然是 O(n/k)每次插入。
我们现在要做的就是找到最优的k ，所以我们要最小化n/k + k .
f(k) = n/k + k, 0 < k <=n
df/dk = n*-1*k^(-2) + 1 = 0
1/n = 1/k^2
n = k^2
sqrt(n) = k
因此，对于 k 的最佳选择我们需要k=sqrt(n) ，我们得到了复杂性:
- 插入:
O(sqrt(n)) - 删除:
O(sqrt(n)) - 选择:
O(log(sqrt(n))) = O(log(n)) - 随机播放:
O(n)
关于c++ - 我应该使用什么数据结构来支持插入、删除和随机选择？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32497989/