Design a data structure that supports insert, delete, search and getRandom in constant time
[Algo] Constant Time Random Picker 获取集合内随机元素 - SegmentFault
private List<String> servers = new ArrayList<String>();
Map<String,Integer> index = new HashMap<String,Integer>();
public void addServer(String name){
servers.add(name);
index.put(name, servers.size()-1);
}
public void removeServer(String name){
Integer pos = index.get(name);
if(pos == null){
throw new IllegalArgumentException();
}
servers.set(pos, servers.get(servers.size()-1));
servers.remove(servers.size()-1);
}
public String getRandom(){
int r = (int)(Math.random()*1000);
return servers.get(r%servers.size());
}
}
Read full article from [Algo] Constant Time Random Picker 获取集合内随机元素 - SegmentFault
Design a data structure that supports following operations in Θ(1) time.
insert(x): Inserts an item x to the data structure if not already present.
remove(x): Removes an item x from the data structure if present.
search(x): Searches an item x in the data structure.
getRandom(): Returns a random element from current set of elements
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); }}设计一个数据结构，支持O(1)时间的查询，增加，删除，和得到其中随机元素的操作，可以认为其中的元素是数字。
要求O(1)时间查询和删除，则想到哈希表，其他的数据结构都要遍历一遍才行。但是getRandom这功能有要求我们必须保持内容的有序，这样我们才能通过随机数的方法得到随机的某个元素。这里我们可以用数组、链表或者树保持有序，但是链表得到第n个元素要O(N)的时间，而树也要logN时间，所以不适合，只有数组。用数组的技巧在于，数组只是保持一个顺序，我们可以哈希表表示一个元素和其在数组中下标的映射关系，保证我们的O(1)查询。而对于删除，我们需要维护一个length变量（用表的大小也行），然后每次删除的时候把要删的数和数组当前标记的“最后”一个元素交换，然后把大小减一，并更新哈希表。取得随机数的话，则是在当前数组有效范围内取随机数就行了。
public class RandomPicker {
Random r;
ArrayList<Integer> arr;
HashMap<Integer, Integer> map;
int length;
public RandomPicker(){
this.r = new Random();
this.arr = new ArrayList<>();
this.map = new HashMap<>();
this.length = 0;
}
public void add(int key){
arr.add(length, key);
map.put(key, length);
length++;
}
public void delete(int key){
// 将要删的数和最后一个交换
int idx = map.get(key);
int tmp = arr.get(length - 1);
arr.set(length - 1, key);
arr.set(idx, tmp);
// 更新元素和下标的对应关系
map.put(tmp, idx);
length--;
}
public int getRandom(){
return arr.get(r.nextInt(length));
}
}- Design a load balancer where you can add,remove and find random server in O(1) time -LoadBalancers.java
private List<String> servers = new ArrayList<String>();
Map<String,Integer> index = new HashMap<String,Integer>();
public void addServer(String name){
servers.add(name);
index.put(name, servers.size()-1);
}
public void removeServer(String name){
Integer pos = index.get(name);
if(pos == null){
throw new IllegalArgumentException();
}
servers.set(pos, servers.get(servers.size()-1));
servers.remove(servers.size()-1);
}
public String getRandom(){
int r = (int)(Math.random()*1000);
return servers.get(r%servers.size());
}
}
Read full article from [Algo] Constant Time Random Picker 获取集合内随机元素 - SegmentFault
