[LeetCode]Insert Delete GetRandom O(1)

插入删除O(1)，我们会想到hashmap + linkedlist，但是要求O(1)的get random显然这无法达到，所以我们要考虑其他的数据结构。显然hashmap还是需要的，那么为了实现O(1)的get random我们可以尝试用array。那么array的缺点是容量是固定的，满了之后我们要把array里的所有元素copy到一个更大的array当中，那么我们还能达到O(1)的时间复杂度么？
我们分析平摊时间(armortized time)，假设array初始容量为1，每次满了之后double size，那么插入n个元素的总的时间复杂度是O(n)。因为我们总共会double log2(n)次array，也就是说总的double的时间复杂度为1 + 2 + 4 + ... + 2^(log2(n)) = O(n)。也就是说平摊到每一次操作上，时间复杂度就是O(1)。所以用dynamic array是可行的，我们不需要自己去implement，因为c++，java都有自带的vector和arraylist。
我们可以保证insert和get random的常数时间，那么delete应该怎么做呢。显然我们不能简单的=地delete然后将后面的所有数向前平移一格。这里我们每次将要删除的数和最后的数交换，更新hashmap，然后删除最后的数即可。代码如下：

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

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