[LeetCode]Random Flip Matrix

这道题显然不可能每次O(N)去生成random，这样太耗费时间。我们可以参考Insert Delete GetRandom O(1)的方法，每一次把取了的和末尾换即可。当然这里我们并不会维护整个区间的数组，我们只需要对每一个取了的数组，重新map到结尾还没有取的数即可。每次和结尾交换的数，可能本身其已经map到了另一个数，注意这种情况即可。每次生成random的时间复杂度为O(1)，代码如下：

	class Solution {
	public:
	Solution(int n_rows, int n_cols) {
	rows = n_rows;
	cols = n_cols;
	n = rows * cols;
	picked = 0;
	}
	vector<int> flip() {
	int end = n - 1 - picked;
	int r = rand() % (end + 1);
	int res = map.find(r) == map.end() ? r : map[r];
	map[r] = map.find(end) == map.end() ? end : map[end];
	++picked;
	return{ res / cols, res % cols };
	}
	void reset() {
	picked = 0;
	map.clear();
	}
	private:
	int rows, cols, n, picked;
	unordered_map<int, int> map;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(n_rows, n_cols);
	* vector<int> param_1 = obj.flip();
	* obj.reset();
	*/

view raw Random Flip Matrix.cpp hosted with ❤ by GitHub

这道题还有另外一种方法，用sqrt decomposition切分区间。这样我们每次generate random的时间复杂度可以降到O(sqrt(N))，代码如下：

	class Solution {
	public:
	Solution(int n_rows, int n_cols) {
	rows = n_rows;
	cols = n_cols;
	n = rows * cols;
	bucketSize = static_cast<int>(sqrt(n));
	int len = n / bucketSize + (n % bucketSize != 0);
	buckets = vector<unordered_set<int>>(len);
	picked = 0;
	}
	vector<int> flip() {
	int r = rand() % (n - picked), curr = 0;
	for (int i = 0; i < buckets.size(); ++i)
	{
	int len = buckets[i].size();
	if (curr + bucketSize - len > r)
	{
	for (int j = 0; j < bucketSize; ++j)
	{
	int idx = i * bucketSize + j;
	if (buckets[i].count(idx))continue;
	if (curr == r)
	{
	buckets[i].insert(idx);
	++picked;
	return{ idx / cols, idx % cols };
	}
	++curr;
	}
	}
	curr += bucketSize - len;
	}
	}
	void reset() {
	picked = 0;
	for (auto& bucket : buckets)
	bucket.clear();
	}
	private:
	int rows, cols, n, picked, bucketSize;
	vector<unordered_set<int>> buckets;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(n_rows, n_cols);
	* vector<int> param_1 = obj.flip();
	* obj.reset();
	*/

view raw Random Flip Matrix_2.cpp hosted with ❤ by GitHub