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

问题描述

我在接受采访时被给了这个问题。您如何回答？

设计在O（1）时间内提供以下操作的数据结构：

• insert


• 删除


• 包含


• 获取随机元素
• 
  

解决方案

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

1. insert（value）：将值附加到数组，我是A中的索引。Set H [value] = i。


2. remove（value）：我们将用A中的最后一个元素替换包含A中的值的单元格。让d成为索引m的数组A中的最后一个元素。让我成为H [value]，数组中的索引值将被删除。设置A [i] = d，H [d] = i，将数组的大小减小1，并从H中删除值。


3. contains（value）：return H.contains （值）


4. getRandomElement（）：let r = random（当前大小的A）。返回A [r]。

由于数组需要自动增加大小，因此将O（1）添加一个元素，但我猜没关系。

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

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

• insert
• remove
• contains
• get random element

解决方案

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): append the value to array and let i be its index in A. Set H[value]=i.
2. remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3. contains(value): return H.contains(value)
4. getRandomElement(): let r=random(current size of A). return A[r].

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屋！