[LeetCode]Random Pick with Blacklist

假设blacklist的size为k，这道题第一个想法应该就是把所有不在blacklist里的数字重新map到[0, N - k)，的区间中。这样我们只需要生成一个在[0, N- k)范围中的数然后找对于map的原来的数字即可。但是鉴于这道题输入的范围，N可以达到10^9，我们是不可能开出这么大的数组的，所以我们要想其他的办法。
第一个想法就是时间换空间，既然没有那么多空间，我们在pick()多花点时间即可，比如我们可以生成一个[0, N - k)的数i，然后找第i个不在blacklist里的数返回。但是这样的话显然每次pick的时间复杂度变为了O(N)，这是我们不能接受的。
有的时候我们需要从另一个角度思考，既然我们存不下N的范围，k的范围我们总是可以存的下的。对于生成的在[0, N - k)中的数i，其可能在blacklist当中，但是如果对于所有在[0, N - k)范围中并且在blacklist当中的数，我们重新map到[N - k, N)范围中另一个不在blacklist的数(显然这两个集合的size是相等的，我们可以做到一一映射)。我们仍然可以达到我们之前所说的效果，并且这个在空间上是完全可行的。
时间复杂度的话，我们要对blacklist进行sort，所以constructor的时间复杂度为O(N * log N)，pick的话为O(1)。空间复杂度O(k)。代码如下：

	class Solution {
	public:
	Solution(int N, vector<int> blacklist) {
	int sz = blacklist.size();
	n = N - sz;
	int i = 0, j = n;
	unordered_set<int> set;
	sort(blacklist.begin(), blacklist.end());
	for(const auto& num : blacklist)set.insert(num);
	while(i < sz && blacklist[i] < n)
	{
	while(set.find(j) != set.end())++j;
	map[blacklist[i++]] = j++;
	}
	}
	int pick() {
	int r = rand() % n;
	if(map.find(r) == map.end())return r;
	else return map[r];
	}
	private:
	unordered_map<int, int> map;
	int n;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(N, blacklist);
	* int param_1 = obj.pick();
	*/

view raw Random Pick with Blacklist.cpp hosted with ❤ by GitHub