这是最近一次采访问题.请设计一个具有插入,删除,随机的数据结构o(1)时间复杂度,数据结构可以是数组等基本数据结构,可以是基本数据结构的修改,也可以是基本数据的组合结构.
将数组与元素的哈希映射组合到数组索引.
插入可以通过附加到数组并添加到哈希映射来完成.
删除可以通过首先查找并删除哈希映射中的数组索引,然后使用数组中的该元素交换最后一个元素,适当地更新前一个元素的索引,并将数组大小减小一个(删除最后一个)元件).
可以通过从数组中返回随机索引来完成随机.
所有操作都需要O(1).
嗯,实际上,它是从预期的哈希冲突(从预期的哈希冲突)O(1)分摊(从调整数组大小),但足够接近.