题目描述:根据矩形面积,随机生成矩形内部的一个点
ref{:target=”_blank”}
采用 前缀和 + 二分
C++ 代码
class Solution {
public:
typedef long long LL;
Solution(vector<vector<int>>& rects) {
// 1.根据面积确定是哪个矩形;2.在矩形中分别rand横坐标、总坐标
rects_ = rects;
int n = rects.size();
prefix_.push_back(0);
for(auto rect : rects) {
// 注意这里计算的是点的个数
int w = rect[2] - rect[0] + 1;
int l = rect[3] - rect[1] + 1;
LL area = w*l;
prefix_.push_back(prefix_.back() + area);
}
}
vector<int> pick() {
// 二分确定是哪个 area,t的范围是 [1, prefix_.back()]
int t = rand() % prefix_.back() + 1;
// l 和 r表示第几个数字
int l = 1, r = rects_.size();
while(l<r){
int mid = l+r>>1;
if(prefix_[mid] >= t) r = mid;
else l = mid+1;
}
int idx = l-1;
const auto& rect = rects_[idx];
int dx = rect[2] - rect[0] + 1;
int dy = rect[3] - rect[1] + 1;
int x = rect[0] + rand() % dx;
int y = rect[1] + rand() % dy;
return {x, y};
}
private:
vector<LL> prefix_;
vector<vector<int>> rects_;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(rects);
* vector<int> param_1 = obj->pick();
*/