设计了一种具有插入、删除、随机O(1)时间复杂度的数据结构，

Question

这是最近的一个面试问题。请设计具有插入、删除、随机o(1)时间复杂度的数据结构，数据结构可以是数组等基本数据结构，可以是基本数据结构的修改，也可以是基本数据结构的组合。

Answer 1

将数组与元素的散列映射组合到数组索引。

插入可以通过附加到数组并添加到散列映射来完成。

删除可以通过以下方式完成:首先查找并删除散列映射中的数组索引，然后用数组中的该元素交换最后一个元素，适当地更新以前的最后一个元素的索引，并将数组大小减少一个(删除最后一个元素)。

可以通过从数组中返回一个随机索引来获得随机值。

所有操作都采用O(1)。

在现实中，它被摊销(通过调整数组的大小)期望(来自预期的散列碰撞) O(1)，但足够接近。

Answer 2

一棵基树就行了。见tree。插入和删除是O(k)，其中k是键的最大长度。如果所有的键都是相同的长度(例如，所有指针)，那么k是一个常数，所以运行时间是O(1)。

为了实现随机化，请保存每个子树(O(k))中树叶总数的记录。树的总叶数记录在树根处。若要随机选择一个，请生成一个随机整数来表示要选择的元素的索引。递归地向下扫描树，始终跟随包含所选元素的分支。您总是知道要选择哪个分支，因为您知道可以从每个子树中获得多少叶子。树的高度不超过k，所以当k是常数时，这是O(k)，或者O(1)。