摘要：思路可以实现时间复杂度的和，但是要求也是，只用是不可以的。但是在里面查找的时间复杂度依然是，可以想到用来记录对应的，这样查找的时间也是常数。用可以保持顺序，但是的时间复杂度是。
380. Insert Delete GetRandom O(1)
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
思路
HashSet可以实现O(1)时间复杂度的insert和remove，但是要求getRandom也是O(1)，只用HashSet是不可以的。在List里面随机找一个数的时间是O(1)，所以可以用list来记录加进去的value，这样insert和getRandom都是O(1)了。remove的操作比较有意思，在一个list里面找到相应的值之后和最后一个位置上的值调换，这个remove就是常数时间了。但是在list里面查找的时间复杂度依然是O(N)，可以想到用hashmap来记录对应的index，这样查找的时间也是常数。
复杂度
Time: O(1), Space: O(N)
代码
Map map;
List list;
Random random;
public RandomizedSet() {
// hashmap to realize insert, remove in O(1), the value is the index in list
map = new HashMap();
// list to realize get random in O(1);
list = new ArrayList();
random = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) return false;
map.put(val, list.size());
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
// change the val with the last one, then delete last one
if(!map.containsKey(val)) return false;
int delete_index = map.get(val);
int last = list.get(list.size() - 1);
// change the last element to the delete place
list.set(delete_index, last);
// update the index in map
map.replace(last, delete_index);
// remove in the list
list.remove((int) list.size() - 1);
// remove in the map
map.remove(val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
if(list.size() == 0) return -1;
return list.get(random.nextInt(list.size()));
}
381. Insert Delete GetRandom O(1) - Duplicates allowed
思路
允许duplication之后麻烦了许多。现在hashmap里面要存所有的index。在remove的时候复杂度要保持O(1)，每次还是要取最后一个值和删除的值交换，所以需要map里面找到最后一个值，之后删除最大的index的时间复杂度是O(1)，同时把index更新成当前删除的值的index之后，所有的index还要保持顺序。
heap
用heap可以保持顺序，但是poll的时间复杂度是O(logN)。
代码
Map> map;
List list;
Random random;
public RandomizedCollection() {
map = new HashMap();
list = new ArrayList();
random = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) {
map.get(val).add(list.size());
list.add(val);
return false;
}
else {
map.put(val, new PriorityQueue<>((a, b) -> b - a));
map.get(val).add(list.size());
list.add(val);
return true;
}
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
int delete_index = map.get(val).peek();
int last = list.get(list.size() - 1);
// update
list.set(delete_index, last);
map.get(last).poll();
map.get(last).add(delete_index);
// delete
list.remove(list.size() - 1);
map.get(val).poll();
if(map.get(val).size() == 0) map.remove(val);
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
LinkedHashSet
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/66477.html
