Readme - Leetcode — ContextQMD

我们手头的随机数生成器rand()%M只能生成[0,M-1]范围内的均匀随机数。如何利用它来实现题目的要求呢？

我们可以将所有的矩形的点都拉成一个序列，然后连续地拼接起来。假设所有矩形所覆盖的点有M个，那么我们通过rand()%M+1就能够得到一个均匀的随机数k，有着相等的概率来代表这M个点的序号（第一个是1号，最后一个是M号）。

接下来我们需要判定k号点是在哪个矩形里。我们只需要利用前缀和的思想，提前准备好一个数组q，其中q[i]表示前i个矩形所覆盖的点的个数，例如[4,10,11]。于是我们在q里面找第一个大于等于k的元素位置，就是k号点所在的矩形的编号i。

有了这个矩形编号i，我们就可以知道k号点在第i个矩形内的相对编号k'，继而通过矩形的宽/高得到其内部第k'个点的行/列位置。