数据结构:插入、删除、包含、获取随机元素，全部在 O(1) [英] Data structure: insert, remove, contains, get random element, all at O(1)

问题描述

我在一次采访中遇到了这个问题.你会怎么回答?

I was given this problem in an interview. How would you have answered?

设计一个数据结构，在 O(1) 时间内提供以下操作:

Design a data structure that offers the following operations in O(1) time:

• 插入
• 删除
• 包含
• 获取随机元素

推荐答案

考虑一个由哈希表 H 和数组 A 组成的数据结构.哈希表的键是数据结构中的元素，值是它们在数据结构中的位置数组.

Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

1. insert(value):将值附加到数组中，并让 i 为其在 A 中的索引.设置 H[value]=i.
2. remove(value):我们将用 A 中的最后一个元素替换包含 A 中值的单元格.让 d 是数组 A 中索引 m 处的最后一个元素.让 i 为 H[value]，要删除的值在数组中的索引.设置A[i]=d，H[d]=i，将数组的大小减一，并从H中移除值.
3. contains(value):返回 H.contains(value)
4. getRandomElement():让 r=random(A 的当前大小).返回 A[r].

由于数组需要自动增加大小，因此添加元素需要分摊 O(1)，但我想这没问题.

since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.

这篇关于数据结构:插入、删除、包含、获取随机元素，全部在 O(1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！