数据结构：插入，删除，包含，得到随机元素，全部在O（1）

面试中我遇到了这个问题。 你会如何回答？

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

• 插
• 去掉
• 包含
• 得到随机元素

Answer 1

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

1. insert（value）：将数值追加到数组中，让我作为它的索引。设置H [value] = i。
2. remove（value）：我们将用A中最后一个元素replaceA中包含值的单元格。let d是数组A中索引为m的最后一个元素。 让我是H [值]，在要删除的值的数组中的索引。 设置A [i] = d，H [d] = i，将数组的大小减1，并从H中去除数值。
3. 包含（值）：返回H.contains（值）
4. getRandomElement（）：let r = random（A的当前大小）。 返回A [r]。

由于数组需要自动增加大小，所以将分解O（1）添加一个元素，但我想这没关系。

Answer 2

O（1）查找意味着散列数据结构 。

通过对比：

• O（1）用O（N）查找插入/删除意味着一个链表。
• O（1）插入，O（N）删除和O（N）查找意味着一个支持数组的列表
• O（logN）插入/删除/查找意味着树或堆。

Answer 3

你可能不喜欢这个，因为他们可能正在寻找一个聪明的解决scheme，但是有时候坚持你的枪支也是值得的… 哈希表已经满足了需求 – 可能比其他任何东西都要好（尽pipe显然是以摊销常量时间和与其他解决scheme不同的妥协）。

棘手的要求是“随机元素”select：在散列表中，您需要扫描或探测这样的元素。

对于封闭散列/开放寻址，任何给定的存储桶被占用的机会是size() / capacity() ，但是关键的是这通常通过哈希表实现保持在一个常数乘法范围内（例如，表可以保持大于其当前的内容由1.2x到〜10x取决于性能/内存调整）。 这意味着我们平均可以search1.2到10个桶 – 完全独立于容器的总大小; 摊销O（1）。

我可以想象两种简单的方法（以及更多的烦杂的方法）：

• 从随机桶中线性search

  • 考虑清空/价值桶ala“–AC —– B – D”：你可以说，即使有利于B，第一个“随机”select也是公平的，因为B没有更多的被看好的可能性但是如果你使用相同的值进行重复的“随机”select，那么显然有B重复使用可能是不可取的（尽pipe如此，问题中没有任何要求）

• 重复尝试随机桶，直到你find一个人口稠密的一个

  • “只有”容量（）/大小（） 平均桶访问（如上） – 但实际上更昂贵，因为随机数的产生是相对昂贵的，无限糟糕，如果无限不可能的最坏情况的行为…
    • 更快的折衷是使用从最初随机select的桶中预先生成的随机偏移量的列表，将它们计入桶计数

这并不是一个好的解决scheme，但是在任何时候维护第二个索引数组的内存和性能开销可能仍然是一个更好的总体折衷。

Answer 4

最好的解决scheme可能是哈希表+数组，它是真正的快速和确定性的。

但最低的评价答案（只是使用哈希表！）实际上也很棒！

• 哈希表与重新哈希，或新的桶select（即每桶一个元素，没有链表）
• getRandom（）重复尝试select一个随机存储区，直到它为空。
• 作为一个失败保险，可能是getRandom（），在N（元素个数）尝试失败后，在[0，N-1]中select一个随机索引i，然后线性遍历哈希表，并select第i个元素。

人们可能不喜欢这个，因为“可能的无限循环”，我也看到很聪明的人也有这个反应，但是这是错误的！ 无限可能的事件不会发生。

假设您的伪随机源的良好行为（对于此特定行为不难确定），并且哈希表总是至less占满20％，很容易看出：

getRandom（）不会尝试超过1000次。 永远不要 。 事实上，这样一个事件发生的概率是0.8 ^ 1000，也就是10 ^ -97，所以我们必须重复10 ^ 88次，才有一次机会发生在十亿次事件中。 即使这个程序在全人类的所有计算机上全天候运行，直到太阳死亡，这也不会发生。

Answer 5

这是一个C＃解决scheme，当我问到同样的问题时，我想到了一些问题。 它与其他标准.NET接口一起实现了Add，Remove，Contains和Random。 这并不是说你在面试时需要这么详细的实施，但是有一个具体的解决scheme来看待…

 using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Threading; /// <summary> /// This class represents an unordered bag of items with the /// the capability to get a random item. All operations are O(1). /// </summary> /// <typeparam name="T">The type of the item.</typeparam> public class Bag<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable { private Dictionary<T, int> index; private List<T> items; private Random rand; private object syncRoot; /// <summary> /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class. /// </summary> public Bag() : this(0) { } /// <summary> /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class. /// </summary> /// <param name="capacity">The capacity.</param> public Bag(int capacity) { this.index = new Dictionary<T, int>(capacity); this.items = new List<T>(capacity); } /// <summary> /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class. /// </summary> /// <param name="collection">The collection.</param> public Bag(IEnumerable<T> collection) { this.items = new List<T>(collection); this.index = this.items .Select((value, index) => new { value, index }) .ToDictionary(pair => pair.value, pair => pair.index); } /// <summary> /// Get random item from bag. /// </summary> /// <returns>Random item from bag.</returns> /// <exception cref="System.InvalidOperationException"> /// The bag is empty. /// </exception> public T Random() { if (this.items.Count == 0) { throw new InvalidOperationException(); } if (this.rand == null) { this.rand = new Random(); } int randomIndex = this.rand.Next(0, this.items.Count); return this.items[randomIndex]; } /// <summary> /// Adds the specified item. /// </summary> /// <param name="item">The item.</param> public void Add(T item) { this.index.Add(item, this.items.Count); this.items.Add(item); } /// <summary> /// Removes the specified item. /// </summary> /// <param name="item">The item.</param> /// <returns></returns> public bool Remove(T item) { // Replace index of value to remove with last item in values list int keyIndex = this.index[item]; T lastItem = this.items[this.items.Count - 1]; this.items[keyIndex] = lastItem; // Update index in dictionary for last item that was just moved this.index[lastItem] = keyIndex; // Remove old value this.index.Remove(item); this.items.RemoveAt(this.items.Count - 1); return true; } /// <inheritdoc /> public bool Contains(T item) { return this.index.ContainsKey(item); } /// <inheritdoc /> public void Clear() { this.index.Clear(); this.items.Clear(); } /// <inheritdoc /> public int Count { get { return this.items.Count; } } /// <inheritdoc /> public void CopyTo(T[] array, int arrayIndex) { this.items.CopyTo(array, arrayIndex); } /// <inheritdoc /> public bool IsReadOnly { get { return false; } } /// <inheritdoc /> public IEnumerator<T> GetEnumerator() { foreach (var value in this.items) { yield return value; } } /// <inheritdoc /> IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } /// <inheritdoc /> public void CopyTo(Array array, int index) { this.CopyTo(array as T[], index); } /// <inheritdoc /> public bool IsSynchronized { get { return false; } } /// <inheritdoc /> public object SyncRoot { get { if (this.syncRoot == null) { Interlocked.CompareExchange<object>( ref this.syncRoot, new object(), null); } return this.syncRoot; } } } 

Answer 6

虽然这已经很老了，但是因为在C ++中没有答案，所以这是我的两分钱。

 #include <vector> #include <unordered_map> #include <stdlib.h> template <typename T> class bucket{ int size; std::vector<T> v; std::unordered_map<T, int> m; public: bucket(){ size = 0; std::vector<T>* v = new std::vector<T>(); std::unordered_map<T, int>* m = new std::unordered_map<T, int>(); } void insert(const T& item){ //prevent insertion of duplicates if(m.find(item) != m.end()){ exit(-1); } v.push_back(item); m.emplace(item, size); size++; } void remove(const T& item){ //exits if the item is not present in the list if(m[item] == -1){ exit(-1); }else if(m.find(item) == m.end()){ exit(-1); } int idx = m[item]; m[v.back()] = idx; T itm = v[idx]; v.insert(v.begin()+idx, v.back()); v.erase(v.begin()+idx+1); v.insert(v.begin()+size, itm); v.erase(v.begin()+size); m[item] = -1; v.pop_back(); size--; } T& getRandom(){ int idx = rand()%size; return v[idx]; } bool lookup(const T& item){ if(m.find(item) == m.end()) return false; return true; } //method to check that remove has worked void print(){ for(auto it = v.begin(); it != v.end(); it++){ std::cout<<*it<<" "; } } }; 

这是一个客户端代码来testing解决scheme。

 int main() { bucket<char>* b = new bucket<char>(); b->insert('d'); b->insert('k'); b->insert('l'); b->insert('h'); b->insert('j'); b->insert('z'); b->insert('p'); std::cout<<b->random()<<std::endl; b->print(); std::cout<<std::endl; b->remove('h'); b->print(); return 0; } 

Answer 7

对于这个问题，我将使用两个数据结构

• HashMap中
• ArrayList / Array / Double LinkedList。

脚步 ：-

1. 插入： – 检查HashMap中是否已经存在X – 时间复杂度O（1）。 如果不存在然后添加ArrayList的末尾 – 时间复杂度O（1）。 将它添加到HashMap中，同时将x作为关键字，最后将索引作为值 – 时间复杂度O（1）。
2. 删除： – 检查X是否存在于HashMap中 – 时间复杂度为O（1）。 如果存在，然后find它的索引，并从HashMap – 时间复杂度O（1）中删除它。 将此元素与ArrayList中的最后一个元素交换并除去最后一个元素 – 时间复杂度O（1）。 更新HashMap中最后一个元素的索引 – 时间复杂度O（1）。
3. GetRandom： – 生成从0到ArrayList的最后一个索引的随机数。 生成的随机索引返回ArrayList元素 – 时间复杂度O（1）。
4. search： – 在HashMap中查看x作为关键字。 – 时间复杂度O（1）。

代码： –

 import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Random; import java.util.Scanner; public class JavaApplication1 { public static void main(String args[]){ Scanner sc = new Scanner(System.in); ArrayList<Integer> al =new ArrayList<Integer>(); HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); while(true){ System.out.println("**menu**"); System.out.println("1.insert"); System.out.println("2.remove"); System.out.println("3.search"); System.out.println("4.rendom"); int ch = sc.nextInt(); switch(ch){ case 1 : System.out.println("Enter the Element "); int a = sc.nextInt(); if(mp.containsKey(a)){ System.out.println("Element is already present "); } else{ al.add(a); mp.put(a, al.size()-1); } break; case 2 : System.out.println("Enter the Element Which u want to remove"); a = sc.nextInt(); if(mp.containsKey(a)){ int size = al.size(); int index = mp.get(a); int last = al.get(size-1); Collections.swap(al, index, size-1); al.remove(size-1); mp.put(last, index); System.out.println("Data Deleted"); } else{ System.out.println("Data Not found"); } break; case 3 : System.out.println("Enter the Element to Search"); a = sc.nextInt(); if(mp.containsKey(a)){ System.out.println(mp.get(a)); } else{ System.out.println("Data Not Found"); } break; case 4 : Random rm = new Random(); int index = rm.nextInt(al.size()); System.out.println(al.get(index)); break; } } } } 

– 时间复杂度O（1）。 – 空间复杂度O（N）。

Answer 8

在C＃3.0 + .NET Framework 4中，genericsDictionary<TKey,TValue>甚至比Hashtable更好，因为您可以使用System.Linq扩展方法ElementAt()来索引基础dynamic数组，其中KeyValuePair<TKey,TValue>元素被存储：

 using System.Linq; Random _generator = new Random((int)DateTime.Now.Ticks); Dictionary<string,object> _elements = new Dictionary<string,object>(); .... Public object GetRandom() { return _elements.ElementAt(_generator.Next(_elements.Count)).Value; } 

然而，据我所知，一个Hashtable（或其字典后代）是不是真正的解决这个问题，因为Put（）只能摊销O（1），不是真正的O（1），因为它是O（N ）在dynamicresize的边界。

有没有真正的解决这个问题？ 我能想到的是，如果你指定一个Dictionary / Hashtable的初始容量，超出了你所期望的数量级，那么你就得到了O（1）操作，因为你不需要resize。

Answer 9

我们可以使用散列来支持Θ（1）时间的操作。

插入（x） 1）通过执行哈希映射查找来检查x是否已经存在。 2）如果不存在，则将其插入到数组的末尾。 3）join哈希表中，将x作为关键字，并将最后一个数组索引作为索引。

删除（x） 1）通过执行哈希映射查找来检查x是否存在。 2）如果存在，则查找其索引并将其从哈希映射中移除。 3）用数组中的这个元素交换最后一个元素，并删除最后一个元素。 交换完成，因为最后一个元素可以在O（1）时间内被移除。 4）更新哈希映射中最后一个元素的索引。

getRandom（） 1）从0到最后一个索引生成一个随机数。 2）在随机生成的索引处返回数组元素。

search（x）在哈希映射中查找x。

Answer 10

我同意匿名。 除了需要获得一个具有相同公平性的随机元素的最后一个要求之外，所有其他要求只能使用一个基于散列的DS来解决。 我将在Java中为此selectHashSet。 一个元素的哈希码模将给我在O（1）时间底层数组的索引号。 我可以使用它来添加，删除和包含操作。

Answer 11

不能我们用Java的HashSet来做这个吗？ 它提供了插入，删除，search全部在O（1）默认情况下。 对于getRandom我们可以利用Set的迭代器来反正随机的行为。 我们只需从集合中迭代第一个元素，而不用担心其余的元素

 public void getRandom(){ Iterator<integer> sitr = s.iterator(); Integer x = sitr.next(); return x; } 

Answer 12

 /* Java program to design a data structure that support folloiwng operations in Theta(n) time a) Insert b) Delete c) Search d) getRandom */ import java.util.*; // class to represent the required data structure class MyDS { ArrayList<Integer> arr; // A resizable array // A hash where keys are array elements and vlaues are // indexes in arr[] HashMap<Integer, Integer> hash; // Constructor (creates arr[] and hash) public MyDS() { arr = new ArrayList<Integer>(); hash = new HashMap<Integer, Integer>(); } // A Theta(1) function to add an element to MyDS // data structure void add(int x) { // If ekement is already present, then noting to do if (hash.get(x) != null) return; // Else put element at the end of arr[] int s = arr.size(); arr.add(x); // And put in hash also hash.put(x, s); } // A Theta(1) function to remove an element from MyDS // data structure void remove(int x) { // Check if element is present Integer index = hash.get(x); if (index == null) return; // If present, then remove element from hash hash.remove(x); // Swap element with last element so that remove from // arr[] can be done in O(1) time int size = arr.size(); Integer last = arr.get(size-1); Collections.swap(arr, index, size-1); // Remove last element (This is O(1)) arr.remove(size-1); // Update hash table for new index of last element hash.put(last, index); } // Returns a random element from MyDS int getRandom() { // Find a random index from 0 to size - 1 Random rand = new Random(); // Choose a different seed int index = rand.nextInt(arr.size()); // Return element at randomly picked index return arr.get(index); } // Returns index of element if element is present, otherwise null Integer search(int x) { return hash.get(x); } } // Driver class class Main { public static void main (String[] args) { MyDS ds = new MyDS(); ds.add(10); ds.add(20); ds.add(30); ds.add(40); System.out.println(ds.search(30)); ds.remove(20); ds.add(50); System.out.println(ds.search(50)); System.out.println(ds.getRandom());`enter code here` } } 

Answer 13

我认为我们可以使用哈希表双向链表。 键将是元素，其关联的值将在双链表中节点。

1. 插入（H，E）：在双链表中插入节点，并inputH [E] = node; O（1）
2. 删除（H，E）：由H（E）得到节点地址，转到该节点的前一个节点，并删除H（E）
3. 包含（H，E）和getRandom（H）显然是O（1）