[LeetCode]Random Point in Non-overlapping Rectangles

这道题和之前的Random Pick with Weight是类似的，我们要按照rectangle整数点的数量所占的权重来分配对应的概率。注意这里我们是找rectangle中所有的整数坐标，整数点的数量并不等于矩形的面积。比如对于矩形[0,0,1,1]其面积只有1，但是却有四个整数点(0, 0), (0, 1), (1, 0), (1, 1)，所以实际整数点的数量是(width + 1) * (height + 1)。我们可以按照之前presum的做法确定一个矩形，然后在矩形里取随机点即可。时间复杂度，preprocess O(n)，pick就是binary search O(log n)。代码如下：

	class Solution {
	public:
	Solution(vector<vector<int>> rects) {
	rectangles = rects;
	int len = rects.size();
	sum = 0;
	for (const auto& rect : rects)
	{
	//integer points
	int width = rect[2] - rect[0] + 1, height = rect[3] - rect[1] + 1;
	int area = width * height;
	sum += area;
	presums.push_back(sum);
	}
	}
	vector<int> pick() {
	int len = presums.size(), r = rand() % sum + 1, lo = 0, hi = len - 1;
	while (lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	if (presums[mid] < r)lo = mid + 1;
	else hi = mid;
	}
	auto rect = rectangles[lo];
	int rx = rect[0] + rand() % (rect[2] - rect[0] + 1), ry = rect[1] + rand() % (rect[3] - rect[1] + 1);
	return{ rx, ry };
	}
	private:
	vector<int> presums;
	vector<vector<int>> rectangles;
	int sum;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(rects);
	* vector<int> param_1 = obj.pick();
	*/

view raw Random Point in Non-overlapping Rectangles_1.cpp hosted with ❤ by GitHub

注意这里我们call了三次rand(), 确定矩形一次，取x, y坐标两次。但实际上我们在生成了一个随机数r之后，确定了矩形rect[i]，我们根据r，如果把rect[i]看成是一个2D array，只需要在rect[i]中找第r - (presum[i] - area)个点就可以，area是rect[i]的整数点的数量。这样我们就可以只call一次rand()。举例而言presum[i] = 11, r = 9, area = 4，rect[i]的左下的点为[2, 2]那么我们就是找rect[i]中第9 - (11 - 4) = 2大的数。如果我们把左下的点看做(0, 0)，按行扫描，我们要找的就是(2, 3)。时间复杂度没有变化，但是我们减少了call rand()的次数，代码如下：

	class Solution {
	public:
	Solution(vector<vector<int>> rects) {
	rectangles = rects;
	int len = rects.size();
	sum = 0;
	for (const auto& rect : rects)
	{
	//integer points
	int width = rect[2] - rect[0] + 1, height = rect[3] - rect[1] + 1;
	int area = width * height;
	sum += area;
	presums.push_back(sum);
	}
	}
	vector<int> pick() {
	int len = presums.size(), r = rand() % sum + 1, lo = 0, hi = len - 1;
	while (lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	if (presums[mid] < r)lo = mid + 1;
	else hi = mid;
	}
	auto rect = rectangles[lo];
	int width = rect[2] - rect[0] + 1, height = rect[3] - rect[1] + 1, area = width * height;
	int x = rect[0] + (r - presums[lo] + area - 1) % width, y = rect[1] + (r - presums[lo] + area - 1) / width;
	return{ x, y };
	}
	private:
	vector<int> presums;
	vector<vector<int>> rectangles;
	int sum;
	};

view raw Random Point in Non-overlapping Rectangles_2.cpp hosted with ❤ by GitHub