题目描述
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains
解题思路
这道题复杂的地方在于，用O(1)的复杂度实现插入和删除。
如果单纯用链表实现，删除的定位操作是O(n)的复杂度；而单纯用数组或者vector的进行操作，插入操作的复杂度也是O(n)。因此，在这里，就得用到哈希表。哈希表的插入和删除操作都是O(1)的复杂度。
然而，即使用了哈希表，也不能完美的解决这道题。由于哈希表无法进行随机访问，因此无法实现getRandom函数。而能够实现线性可能性随机访问的结构只有之前提到的vector或者数组。
因此，这道题中，我们需要结合哈希表和vector。
由于题目要求可能存取相同的数字，因此哈希表采用拉链的方式扩展。
在插入一个新的数字到vector中时，哈希表对应键值记录下它的下标，如果有多个下标则用拉链的方法依次存储。
而在删除时，在链表中移去对应数字的下标；在vector中，先与最后一个元素交换（如果自己是最后一个元素则不需要交换），再移掉vector的最后一个元素。这里要注意，当与最后一个元素交换时，这个元素在链表中的下标也要相应的做出改变。
时间复杂度分析
在插入操作中，插入到vector中的复杂度是O(1)；哈希表定位到对应链表的复杂度是O(1)，将下标插入到链表的操作，由于重复元素不多，因此复杂度也是O(1)。
在删除操作中，移除链表元素的复杂度和插入一致，为O(1)；交换和移除vector最后一个元素的复杂度也为O(1)。
因此，算法中任意一个操作的复杂度都是O(1)。
源码
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() { }
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
// cout << "insert " << val << "\n----------\n";
bool isExist = nums_pos.find(val) != nums_pos.end();
int newIndex = nums.size();
nums_pos[val].push_back(newIndex);
nums.push_back(val);
//display(nums_pos);
//display(nums);
return !isExist;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
bool isExist = nums_pos.find(val) != nums_pos.end();
// cout << "remove " << val << "\n----------\n";
if (isExist) {
int index = nums_pos[val].back();
nums_pos[val].pop_back();
if (nums_pos[val].empty()) {
nums_pos.erase(val);
}
if (index != nums.size() -1) {
nums_pos[nums.back()].remove(nums.size() - 1);
int temp = nums.back();
nums.back() = nums[index];
nums[index] = temp;
nums_pos[temp].push_back(index);
}
nums.pop_back();
//display(nums_pos);
//display(nums);
return isExist;
} else {
return isExist;
}
}
/** Get a random element from the collection. */
int getRandom() {
return nums[rand() % nums.size()];
}
private:
vector nums;
unordered_map> nums_pos;
};
