数据结构：插入，删除，包含，获取随机元素，全部在O（1）
||
采访中给了我这个问题。您将如何回答？
设计一个数据结构，以在O（1）时间内提供以下操作：
插
去掉
包含
获得随机元素
没有找到相关结果
已邀请:
13 个回复
募磷
屠创氓读叔
粱委教
，但至关重要的是，哈希表实现通常将其保持在恒定的乘法范围内（例如，该表可以比其当前内容大1.2） x至〜10x，具体取决于性能/内存调整）。这意味着我们平均可以搜索1.2到10个桶-完全独立于容器的总大小；摊销O（1）。 我可以想象出两种简单的方法（还有很多更巧妙的方法）： 从随机桶中线性搜索 考虑空/值存储桶ala \“-AC ----- B--D \”：您可以说第一个“ random”选择是公平的，即使它偏爱B，因为B不再比其他元素更容易受到偏爱的可能性，但是如果您使用相同的值进行重复的“随机”选择，那么显然反复受到偏爱B可能是不希望的（尽管，问题中甚至没有要求概率） 反复尝试随机存储桶，直到找到一个填充的桶 “仅”访问的平均存储桶容量（）/大小（如上所述）-但实际上更昂贵，因为随机数生成相对昂贵，并且如果无限不可能的最坏情况行为则无限坏... 更快的折衷方法是使用从初始随机选择的存储桶中预先生成的随机偏移量列表，将其％添加到存储桶计数中 这不是一个很好的解决方案，但是与始终保持第二个索引数组的内存和性能开销相比，这可能是一个更好的总体折衷方案。超可林
坍锭嘉韭蓝
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; } } } }爆山
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<T>\"/> class. /// </summary> public Bag() : this(0) { } /// <summary> /// Initializes a new instance of the <see cref=\"Bag<T>\"/> 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<T>\"/> 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; } } }刷骸码
#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<<\" \"; } } };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; }恋裂
扩展方法来索引存储元素的基础动态数组：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; }济畦刨
枫湃揩乾纲
骨乏唯瓜
public void getRandom(){ Iterator<integer> sitr = s.iterator(); Integer x = sitr.next(); return x; }莽缓逢
/* 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` } }联课