[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)。代码如下：

注意这里我们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()的次数，代码如下：