RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in averageO(1) time complexity.
Example 1:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.
Solution:
就是说就是让我们实现如下一个类：
class RandomizedSet {
public:
/** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
bool insert(int val) {}
/** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
bool remove(int val) {}
/** 从集合中等概率地随机获得一个元素 */
int getRandom() {}
}
本题的难点在于两点：
1、插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)。
2、getRandom 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n。
如果仅实现insert/remove的话，那么可以直接用哈希表解决。 使用（动态）数组(vector in C++, list in Python and ArrayList in Java)可以很方便地实现getRandom操作，只要先随机取一个下标，然后返回该下标对应的元素即可。 因此考虑将这两种数据结构结合起来，用一个哈希表和一个数组来维护集合中的元素。
class RandomizedSet {
public:
// 存储元素的值
vector<int> nums;
// 记录每个元素对应在 nums 中的索引
unordered_map<int,int> valToIndex;
bool insert(int val) {
// 若 val 已存在，不用再插入
if (valToIndex.count(val)) {
return false;
}
// 若 val 不存在，插入到 nums 尾部，
// 并记录 val 对应的索引值
valToIndex[val] = nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
// 若 val 不存在，不用再删除
if (!valToIndex.count(val)) {
return false;
}
// 先拿到 val 的索引
int index = valToIndex[val];
// 将最后一个元素对应的索引修改为 index
valToIndex[nums.back()] = index;
// 交换 val 和最后一个元素
swap(nums[index], nums.back());
// 在数组中删除元素 val
nums.pop_back();
// 删除元素 val 对应的索引
valToIndex.erase(val);
return true;
}
int getRandom() {
// 随机获取 nums 中的一个元素
return nums[rand() % nums.size()];
}
};
JAVA Version:
public class RandomizedSet {
List<Integer> list;
Map<Integer, Integer> map;
Random random;
public RandomizedSet() {
// do intialization if necessary
// 用一个list存数，用一个HashMap记录下<val, index> 数对应的坐标(numToIndex)
list = new ArrayList<>();
map = new HashMap<>();
random = new Random();
}
/*
* @param val: a value to the set
* @return: true if the set did not already contain the specified element or false
*/
public boolean insert(int val) {
if(map.containsKey(val)){
return false;
}
list.add(val);
map.put(val, list.size()-1);
return true;
}
/*
* @param val: a value from the set
* @return: true if the set contained the specified element or false
*/
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
int index = map.get(val);
// list.remove(index);
// swap非常神来之笔，可以保证list中其他元素的index order不变，
// 用map去numToIndex获取的数也是正确的数，
// 但是map里面已经remove里这个元素的numToIndex，所以不会找到这个元素的
Collections.swap(list, index, list.size()-1);
map.put(list.get(index), index);
map.remove(val);
list.remove(list.size()-1);
return true;
}
/*
* @return: Get a random element from the set
*/
public int getRandom() {
int r = random.nextInt(list.size());
// System.out.println(list.get(r));
return list.get(r);
}
}