题目：
Design a data structure that supports all following operations in averageO(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.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1); // Returns false as 2 does not exist in the set.
randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2); // getRandom should return either 1 or 2 randomly.
randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1); // 2 was already in the set, so return false.
randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
分析：
设计一个数据结构支持以下几个操作。
insert(val): 当元素 val 不存在时，向集合中插入该项。remove(val): 元素 val 存在时，从集合中移除该项。getRandom: 随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
我们使用HashMap来支持插入和移除操作，利用数组来支持对数据的随机访问。插入元素时，将val和该val在数组中索引值存入map中，新插入的元素实际上在数组中的索引就是数组还有元素的个数，将元素加到动态数组的尾端。
移除元素时，为了能够达到O(1)，除了将val在map中移除，还要对数组进行操作，如果单纯的将val所对应的索引处的元素删除，由于后续的所有元素都要向前移动，这样会浪费大量的时间。我们知道数组移除最后一个元素的时间复杂度时O(1)，我们将要移除的元素和数组的最后一个元素交换，也可以将最后一个元素覆盖到要移除元素的位置，同时修改最后一个元素在map中对应的索引，最后删除掉数组最后一个元素，就可以保证常数时间的移除操作。最后在数组大小的范围内产生随机数，返回对应的元素，即可实现随机访问。
程序:
C++
class RandomizedSet {
public:
/** Initialize your data structure here. */
RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if(m.count(val))
return false;
m[val] = v.size();
v.push_back(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if(!m.count(val))
return false;
int index = m[val];
m[v.back()] = index;
v[index] = v.back();
m.erase(val);
v.pop_back();
return true;
}
/** Get a random element from the set. */
int getRandom() {
int index = rand() % v.size();
return v[index];
}
private:
unordered_map<int, int> m;
vector<int> v;
};
Java
class RandomizedSet {
/** Initialize your data structure here. */
public RandomizedSet() {
}
/** 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) {
if(!map.containsKey(val))
return false;
int index = map.get(val);
map.put(list.get(list.size()-1), index);
list.set(index, list.get(list.size()-1));
list.remove(list.size()-1);
map.remove(val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Random r = new Random();
return list.get(r.nextInt(list.size()));
}
private HashMap<Integer, Integer> map = new HashMap<>();
private ArrayList<Integer> list = new ArrayList<>();
}