Insert Delete GetRandom O(1) - Duplicates allowed

这道题和Insert Delete GetRandom O(1)是类似的，区别在于允许重复的数。我们的思路是类似的，只不过hashmap存的不是数字和对应的index了，而是数数字和hashset，hashset里存了所有的index。删除的时候我们只需要从hashset里随便取一个出来和末尾的数交换即可，代码如下:

	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) {
	bool ret = m_map.find(val) == m_map.end()? true: false;
	m_nums.push_back(val);
	m_map[val].insert(m_nums.size() - 1);
	return ret;
	}
	/** Removes a value from the collection. Returns true if the collection contained the specified element. */
	bool remove(int val) {
	if(m_map.find(val) == m_map.end())
	return false;
	int idx = *(m_map[val].begin()), len = m_nums.size(), num = m_nums[len - 1];
	swap(m_nums[idx], m_nums[len - 1]);
	m_nums.pop_back();
	m_map[val].erase(idx);
	if(m_map[val].empty())m_map.erase(val);
	if(idx != len - 1)
	{
	m_map[num].erase(len - 1);
	m_map[num].insert(idx);
	}
	return true;
	}
	/** Get a random element from the collection. */
	int getRandom() {
	int len = m_nums.size();
	if(!len)return 0;
	int random = rand() % (len);
	return m_nums[random];
	}
	private:
	unordered_map<int, unordered_set<int>> m_map;
	vector<int> m_nums;
	};
	/**
	* Your RandomizedCollection object will be instantiated and called as such:
	* RandomizedCollection obj = new RandomizedCollection();
	* bool param_1 = obj.insert(val);
	* bool param_2 = obj.remove(val);
	* int param_3 = obj.getRandom();
	*/

view raw Insert Delete GetRandom O(1) - Duplicates allowed.cpp hosted with ❤ by GitHub