LeetCode Insert Delete GetRandom O(1) - Duplicates allowed

LeetCode Insert Delete GetRandom O(1) - Duplicates allowed

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. 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.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

这一题在LeetCode Insert Delete GetRandom O(1)的基础上,增加了有重复元素的约束。还是用数组+Hash实现,但是Hash表中不再只是存储单个元素的下标了,而是存储所有相同元素的下标的集合,采用最大堆(priority_queue)来存储相同元素的下标集合。

插入时,数值插入到数组末尾,下标插入到hash表中该数值对应的最大堆中,如果堆原来为空的话,说明这是第一次插入该数值。删除时,取出val在数组中的最大下标(priority_queue.top()即为堆中最大值),如果不是数组末尾,则和数组末尾的数值交换,同时更新原数组末尾数值的下标最大堆,最后删掉数组末尾的数。产生随机数同样好办,直接rand下标。

完整代码如下:

class RandomizedCollection {
private:
	unordered_map<int, priority_queue<int>> hash;
	vector<int> nums;
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) {
		hash[val].push(nums.size());
		nums.push_back(val);
		return hash[val].size() == 1;
	}

	/** Removes a value from the collection. Returns true if the collection contained the specified element. */
	bool remove(int val) {
		if (hash[val].empty())return false;
		int pos = hash[val].top();
		hash[val].pop();
		if (pos != nums.size() - 1) {
			nums[pos] = nums[nums.size() - 1];
			hash[nums[pos]].pop();
			hash[nums[pos]].push(pos);
		}
		nums.pop_back();
		return true;
	}

	/** Get a random element from the collection. */
	int getRandom() {
		return nums[rand() % nums.size()];
	}
};

本代码提交AC,用时85MS。

但是为什么要用最大堆来存储相同数值的下标集合呢,而且最大堆的插入和删除效率不是O(1)的呀,难道是因为相同的数比较少?所以每个数值的下标堆很小,所以插入和删除的复杂度近似为O(1)?

那么能否用数组来存储相同数值的下标集合呢,即用unordered_map<int, vector> hash,答案是不可以。举例如下:

假设经过了6次插入之后,数组为[10,10,20,20,30,30],此时不同数值的下标集合为:

  • 10:[0,1]
  • 20:[2,3]
  • 30:[4,5]

此时删除10,则会把第二个10删掉,同时把末尾的30放到第二个10的位置,数组变为[10,30,20,20,30],此时下标集合为:

  • 10:[0]
  • 20:[2,3]
  • 30:[4,1]

如果此时再次删除10,则会把第一个10删掉,同时把末尾的30放到第一个10的位置,数组变为[30,30,20,20],但是此时的下标集合变为了:

  • 10:[]
  • 20:[2,3]
  • 30:[4,0]

即30的下标集合出现了错误,因为存储下标集合的数据结构是vector,O(1)的删除只能是pop_back(),但是这样并不能保证删掉最大的下标,本来这次我们是要删掉最大的下标4的,但是结果却删了0,依然保存了已不存在的下标4。所以用最大堆的目的就是为了每次删除都删掉最大的下标。

但是最大堆的插入和删除毕竟不是O(1),再次使用Hash存储下标才是真正的O(1)做法,即用unordered_map> hash,这样的话,在上面的例子中,我可以用O(1)的时间删除下标4。

class RandomizedCollection {
private:
	unordered_map<int, unordered_set<int>> hash;
	vector<int> nums;
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) {
		hash[val].insert(nums.size());
		nums.push_back(val);
		return hash[val].size() == 1;
	}

	/** Removes a value from the collection. Returns true if the collection contained the specified element. */
	bool remove(int val) {
		if (hash[val].empty())return false;
		int pos = *hash[val].begin();
		hash[val].erase(pos);
		if (pos != nums.size() - 1) {
			nums[pos] = nums[nums.size() - 1];
			hash[nums[pos]].erase(nums.size() - 1);
			hash[nums[pos]].insert(pos);
		}
		nums.pop_back();
		return true;
	}

	/** Get a random element from the collection. */
	int getRandom() {
		return nums[rand() % nums.size()];
	}
};

本代码提交AC,用时79MS。

Leave a Reply

Your email address will not be published. Required fields are marked *