设计高度优化的数据结构来执行插入、删除和getRandom三个操作
我刚刚进行了一次软件面试。其中一个问题是以高度优化的方式使用三种方法（插入、删除和获取随机）设计任何数据结构。面试官让我考虑一种数据结构的组合来设计一个新的数据结构。插入可以设计任何方式，但随机和删除我需要得到具体元素的位置。他给了我一个提示，让我考虑一下需要最少时间进行排序的数据结构。
欢迎任何回答或讨论。。。。
共有3个答案
排序时间最少的数据结构是排序数组。
get_random（）是二分搜索，所以O（log n）。
插入（）和删除（）涉及添加/删除相关元素，然后再使用，即O（n log n），例如可怕的。
我认为他的暗示很糟糕。你的面试可能很糟糕。
一棵树在这里可能很管用。顺序log（n）insert和delete，并选择random也可以是log（n）：从根节点开始，在每个连接处随机选择一个子节点（按每个子节点的叶节点总数加权），直到到达一个叶。
让t成为要存储在数据结构中的元素的类型。有一个可扩展的数组元素，其中包含没有特定顺序的所有元素。有一个哈希表index，将t类型的元素映射到它们在元素中的位置。
- 插入意味着
- 借助索引查找元素中元素的位置
- 用元素的最后一个元素覆盖元素
- 更新索引：删除映射（f，index.size（））并插入（f，i）
假设哈希表非常适合类型为t的元素，那么所有三个操作都是O（1）。
注意数据结构中有0或1个元素的情况。
-
我有一种情况，我需要一个可以添加字符串的数据结构。这个数据结构非常大。 我需要它具有的特定品质是： 获取（索引） 删除最初在超过限制时添加的一定数量的条目。（LIFO） 我尝试使用 ArrayList，但删除操作为 o（n），对于 linkedList，遍历或 get（） 操作将为 o（n）。 我还有哪些其他选择？
-
我现在正在解决一个编码挑战，我有一个解决方案，但是为了让它工作，我需要一个支持四个操作的数据结构： 插入O（对数（N）） 我尝试使用Java的来解决它，它可以通过添加，，和（并检查最后两个的大小）来支持这些操作。但是这个解决方案太慢了。我还没有检查时间复杂性，但是我有一种感觉，不能在对数时间内运行（或者运行效率低下）。 有人知道我可以实现一个数据结构来支持这些操作吗？这可能吗？如果它是树形的，最好
-
7.4.1. 设计选择 7.4.2. 使你的数据尽可能小 7.4.3. 列索引 7.4.4. 多列索引 7.4.5. MySQL如何使用索引 7.4.6. MyISAM键高速缓冲 7.4.7. MyISAM索引统计集合 7.4.8. MySQL如何计算打开的表 7.4.9. MySQL如何打开和关闭表 7.4.10. 在同一个数据库中创建多个表的缺陷 7.4.1. 设计选择 MySQL将行数据和索
-
我正在寻找一个非常具体的数据结构。假设已知元素的最大数量。所有元素都是整数。允许复制。行动包括： 查阅如果我插入n个元素，是最小的元素，是最高的元素是k个最小的元素。所需运行时间： 插入。执行排序的插入，其中是一个整数。所需的运行时： 删除。删除（i）删除第i个元素。所需的运行时： 我想要一种数据结构，是这样吗？我的问题与语言无关，但我用C语言编写代码。
-
问题内容： 最终，我实现的框架每个表使用三个触发器，这些触发器基于表的更改插入审核信息。 我的插入和删除审核触发器非常简单。但是，更新触发器要复杂得多，因为触发器必须检查以确定每个列是否在审核控制之下，然后根据“插入”和“已删除”列中的列值是否相等执行插入操作，因为我不想写不必要的审核记录。最终，我想知道是否有一种编写存储过程的方法，该方法允许我动态执行下面的insert语句，从而减少触发器中的代
-
问题内容： 我刚刚开始研究通过索引优化查询，因为SQL数据正在快速增长。我查看了优化器如何通过SSMS中的执行计划处理查询，并注意到正在使用Sort运算符。我听说排序运算符表示查询中的设计不正确，因为可以通过索引过早地进行排序。因此，这是一个示例表和数据，类似于我正在做的事情： 这是一个示例查询： 我创建了一个非聚集索引来帮助加快查询速度： 为了建立IX_Store索引，我从简单的谓词开始 然后我