我刚刚接受了软件面试。其中一个问题是以高度优化的方式设计具有三种方法 insert、delete 和 getRandom 的任何数据结构。面试官让我想出一种数据结构的组合来设计一个新的。无论如何都可以设计插入，但对于随机和删除，我需要获取特定元素的位置。他给了我一个提示，让我考虑一下排序所需时间最短的数据结构。
欢迎任何回答或讨论......
问问题
1090 次
5 回答
3
让t成为您要存储在数据结构中的元素的类型。有一个包含所有元素的可扩展数组elements，没有特定的顺序。有一个哈希表indices，将类型元素映射t到它们在elements.
- 插入
e装置e在末尾添加elements（即push_back），得到它的位置i- 将映射
(e,i)插入到 `indices
- 删除
e手段- 找到感谢
i的位置eelementsindices - 用最后一个
e元素覆盖felements - 更新
indices：删除映射(f,indices.size())并插入(f,i)
- 找到感谢
- 随机绘制一个元素（将其留在数据结构中，即它是
peek，不是pop）只是i在其中绘制一个整数[0,elements.size()[并返回elements[i].
假设哈希表非常适合您的 type 元素t，那么所有三个操作都是 O(1)。
请注意数据结构中有 0 个或 1 个元素的情况。
于 2012-06-27T12:26:46.580 回答
2
一棵树可能在这里工作得很好。命令 log(n) 插入和删除，并选择 random 也可以是 log(n)：从根节点开始，在每个连接处随机选择一个子节点（由每个子节点的叶子节点总数加权），直到达到叶子。
于 2012-06-27T09:07:16.183 回答
0
排序所需时间最少的数据结构是有序数组。
get_random() 是二分查找，所以 O(log n)。
insert() 和 delete() 涉及添加/删除有问题的元素，然后重新使用，这是 O(n log n)，例如可怕的。
我认为他的暗示很糟糕。你的面试可能很糟糕。
于 2012-06-27T09:19:20.720 回答
0
可能是堆（数据结构）
于 2012-06-28T08:16:17.470 回答
0
我觉得你可以使用一些平衡版本的树，比如红黑树。这将给出 O(log n) 的插入和删除时间。为了获取随机元素，您可能可以有一个额外的哈希表来跟踪树结构中的元素。
于 2012-06-27T10:02:15.867 回答