设计一个在Θ（1）时间内支持以下操作的数据结构。 插入（x）：在数据结构中插入x项（如果尚未存在）。 移除（x）：从数据结构中移除项x（如果存在）。 搜索（x）：搜索数据结构中的项目x。 getRandom（）：从当前元素集中返回一个随机元素
null
我们可以使用 散列 在Θ（1）时间内支持前3个操作。如何进行第四次手术？其想法是将可调整大小的数组（Java中的ArrayList，C中的vector）与哈希一起使用。 可调整大小的数组支持插入Θ（1）摊销时间复杂度 。要实现getRandom（），我们只需从0到size-1（size是当前元素的数量）中选择一个随机数，然后返回该索引处的元素。哈希映射将数组值存储为键，将数组索引存储为值。 以下是详细操作。 插入（x） 1） 通过哈希映射查找来检查x是否已经存在。 2） 如果不存在，则将其插入数组末尾。 3） 此外，在哈希表中添加x作为键，最后一个数组索引作为索引。 移除（x） 1） 通过哈希映射查找来检查x是否存在。 2） 如果存在，则找到它的索引并将其从哈希映射中删除。 3） 将数组中的最后一个元素与此元素交换，然后删除最后一个元素。 交换完成是因为最后一个元素可以在O（1）时间内移除。 4） 更新哈希映射中最后一个元素的索引。 getRandom（） 1） 生成从0到最后一个索引的随机数。 2） 在随机生成的索引处返回数组元素。 搜索（x） 在哈希映射中查找x。 下面是数据结构的实现。
C++
/* C++ program to design a DS that supports following operations in Theta(n) time a) Insert b) Delete c) Search d) getRandom */ #include<bits/stdc++.h> using namespace std; // class to represent the required data structure class myStructure { // A resizable array vector < int > arr; // A hash where keys are array elements and values are // indexes in arr[] map < int , int > Map; public : // A Theta(1) function to add an element to MyDS // data structure void add( int x) { // If element is already present, then nothing to do if (Map.find(x) != Map.end()) return ; // Else put element at the end of arr[] int index = arr.size(); arr.push_back(x); // and hashmap also Map.insert(std::pair< int , int >(x, index)); } // function to remove a number to DS in O(1) void remove ( int x) { // element not found then return if (Map.find(x) == Map.end()) return ; // remove element from map int index = Map.at(x); Map.erase(x); // swap with last element in arr // then remove element at back int last = arr.size() - 1; swap(arr[index], arr[last]); arr.pop_back(); // Update hash table for new index of last element Map.at(arr[index]) = index; } // Returns index of element if element is present, otherwise null int search( int x) { if (Map.find(x) != Map.end()) return Map.at(x); return -1; } // Returns a random element from myStructure int getRandom() { // Find a random index from 0 to size - 1 srand ( time (NULL)); int random_index = rand () % arr.size(); // Return element at randomly picked index return arr.at(random_index); } }; // Driver main int main() { myStructure ds; ds.add(10); ds.add(20); ds.add(30); ds.add(40); cout << ds.search(30) << endl; ds. remove (20); ds.add(50); cout << ds.search(50) << endl; cout << ds.getRandom() << endl; } // This code is contributed by Aditi Sharma |
JAVA
/* Java program to design a data structure that support following 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 values 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 element is already present, then nothing 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()); } } |
Python3
''' Python program to design a DS that supports following operations in Theta(n) time: a) Insert b) Delete c) Search d) getRandom ''' import random # Class to represent the required # data structure class MyDS: # Constructor (creates a list and a hash) def __init__( self ): # A resizable array self .arr = [] # A hash where keys are lists elements # and values are indexes of the list self .hashd = {} # A Theta(1) function to add an element # to MyDS data structure def add( self , x): # If element is already present, # then nothing has to be done if x in self .hashd: return # Else put element at # the end of the list s = len ( self .arr) self .arr.append(x) # Also put it into hash self .hashd[x] = s # A Theta(1) function to remove an element # from MyDS data structure def remove( self , x): # Check if element is present index = self .hashd.get(x, None ) if index = = None : return # If present, then remove # element from hash del self .hashd[x] # Swap element with last element # so that removal from the list # can be done in O(1) time size = len ( self .arr) last = self .arr[size - 1 ] self .arr[index], self .arr[size - 1 ] = self .arr[size - 1 ], self .arr[index] # Remove last element (This is O(1)) del self .arr[ - 1 ] # Update hash table for # new index of last element self .hashd[last] = index # Returns a random element from MyDS def getRandom( self ): # Find a random index from 0 to size - 1 index = random.randrange( 0 , len ( self .arr)) # Return element at randomly picked index return self .arr[index] # Returns index of element # if element is present, # otherwise none def search( self , x): return self .hashd.get(x, None ) # Driver Code if __name__ = = "__main__" : ds = MyDS() ds.add( 10 ) ds.add( 20 ) ds.add( 30 ) ds.add( 40 ) print (ds.search( 30 )) ds.remove( 20 ) ds.add( 50 ) print (ds.search( 50 )) print (ds.getRandom()) # This code is contributed # by Saurabh Singh |
输出：
2340
本文由 马尼什·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
