首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

常数时间插入、删除和获取随机元素

题目要求实现对于插入与删除操作时间复杂度为O(1)的数据结构,很容易联想到链表与哈希表,题目还要求随机返回值的时间复杂度也是O(1),而单纯的链表与哈希表都无法满足这个要求,且在给定值的情况下链表的查找时间复杂度为O(n),不适用于本题,所以需要使用哈希表配合数组来实现,将值作为哈希表的key,在数组中的索引作为哈希表的value,这样对于insert与getRandom操作的时间复杂度都是O(1),对于remove操作需要将传入的value在数组中的索引值取出,然后将数组中最后一个值覆盖到这个索引,然后更改最后一个值在哈希表中的索引,最后删除数组中最后一个值以及哈希表中该值作为的key,这样就实现了O(1)复杂度的remove操作。首先在构造函数定义对象作为哈希表以及数组,在insert操作中,如果哈希表中已存在该值,则直接返回false,如果不存在则添加该值到哈希表作为key并将数组的长度作为值,在数组后追加该值,返回true,在remove操作中首先判断如果不存在该值则直接返回false,如果存在值则取出该值的index,然后将数组的最后一个值取出并在哈希表中将该值作为key,将index作为值,即将最后一个值覆盖到要删除的位置,然后将哈希表中要删除的值的索引删除,将数组的该值位置覆盖为最后一个值,然后删除数组中最后一个值,在getRandom操作中直接返回一个随机的数组值即可。

03
领券