随机生成

给定圆的圆心坐标和半径，给出均匀采样圆内点的随机点坐标^[1]。拒绝采样，考虑圆的外接正方形，在外接正方形均匀采样，采样正方形的内部点直到那个点是圆内的点。C++的随机数生成用到默认随机数生成引擎类default_random_engine，本题用到均匀分布浮点数采样器uniform_real_distribution<double>类，生成随机浮点数时用uniform_real_distribution<double>(default_random_engine)

等概率随机返回nums中等于target的元素的索引。[2]哈希表加随机的方法比较简单想。
延伸的另一种方法：水塘采样：假设水塘容纳的元素容量是k,面对一个长度为N（N>k)的元素流，如何在不加载所有元素的情况下等概率取出其中的k个元素，空间复杂度为O（1），前述的哈希表方法加载了nums的所有元素，这种情境下的解决方法就是水塘采样。元素流的前k个元素很好安排，刚好全部被取出放到水塘中，当第k+1个元素过来，如何决定新来的第k+1元素等概率地进入水塘？k+1个元素等概率取一个位于水塘外，从1到k+1随机取一个整数，若整数在1到k范围内，则替换第整数元素为第k+1元素，则前k个元素的某个元素c留在水塘的概率1*k/(k+1)，整数不等于c则c仍会在水塘，第k+1元素留在水塘的概率k/(k+1)，若整数不等于k+1则第k+1元素会在水塘，等概率。当第k+2个元素过来，从1到k+2随机取一个整数，若整数在1到k范围内，则替换水塘中第整数元素为第k+2元素，则前k+1个元素的某个元素c留在水塘的概率k/(k+1)*(k+1)/(k+2)，上次决定去留时c留在水塘的概率为k/(k+1)，这次仍然整数不等于c则c仍会在水塘（如果当初第k+1元素留在了水塘，当作第k+1元素继承了它替换的元素名号，也可以理解为水塘的坑位从1到k,各个元素要用的是水塘的某个坑位，占着这个坑位表示它还在水塘中，当新来的元素过来掷色子看能否落到这k个坑位中，若投中，老的元素就要让坑），第k+2个元素留在水塘的概率k/(k+2)。依此类推，若第n元素过来（n>k），则需要在1到n随机选择一个整数，若整数在1到k范围内，则设置水塘中整数坑位为第n元素，前n-1个元素的某个元素c留在水塘的概率k/(n-1)*(n-1)/n=k/n，上一个元素过来时c在水塘的概率是k/(n-1),这次只要没有随机选择到c就仍在水塘，第n元素拿到1到k就在水塘，概率k/n。经过推理证明可知水塘采样的采样原理是第n（n>k）元素过来，若idx=randint(1,n)在[1,k]范围内，替换水塘idx坑位元素为第n元素，如此操作直到遍历完nums,水塘里的元素就是等概率抽取的N中k个元素。
对于这道题，k=1,且元素流里面的元素需要等于target，水塘里的数表示索引。
构造哈希表的时间复杂度O（n），空间复杂度O（n），取出一个值时间复杂度O（1）；水塘采样不用构造什么东西，空间复杂度O（1），即常量k，取出一个值时间复杂度O（n），需要遍历nums。对于具体应用场景，权衡时间和空间的使用容量，比如需要多次取出一个值，采用哈希表的方法更好些，更快，跟采用的方法的难度无关。

0到n-1的数列有几个数列入黑名单，不能返回，求如何等概率返回数列中能返回的数。[3]
方法一：构建黑名单映射。黑名单里的数有m个，则能返回的数为n-m个，建立黑名单中小于n-m的整数到能返回的大于等于n-m的数之间的映射，在[0,n-m)范围找随机数，要么返回映射里对应的数，要么本身能返回。建立映射的过程：

unordered_set<int> s;
for(int i=size;i<n;i++)s.insert(i);
for(int& bl:blacklist)s.erase(bl);
unordered_set<int>::iterator sit=s.begin();
for(int& bl:blacklist){
    if(bl<size)m[bl]=*sit++;
}

方法二：二分查找。设[0,n-m)范围产生的随机数是k,本题即找白名单中的k号数，即找到白名单的前k个数，可以利用黑名单的数来划分。从小到大排序黑名单的数。二分查找白名单的前k个数的界限，设low=0,high=m，当high-low>1时，循环执行下述查找，mid=(low+high)/2;if(blacklist[mid]-mid<=k)low=mid;else high=mid;。blacklist[mid]-mid表示白名单中小于blacklist[mid]的元素数量，比如说blacklist[2]=7，则白名单中小于7的元素有5个，因为小于7的元素有7个，黑名单里有2个。通过二分找满足blacklist[i]-i<=k的i的上界。f(x)=blacklist[x]-x是非严格递增函数，记y0=blacklist[x0]-x0，blacklist[x1]=blacklist[x0]+d(d>=1),x1=x0+1,则y1=blacklist[x1]-x1-blacklist[x0]+x0=d-1>=0。执行完二分查找，若high!=low+1，说明没进入过二分查找，说明m==0,没有黑名单，那就按k返回，注意若没有黑名单的存在，此题索引和值指向的值相同，就算有黑名单，我们也可以使用算式使得索引往值上靠。若blacklist[low]-low<=k，返回k+low+1,白名单k号数前面有k个数，黑名单里有low+1个数，黑名单里的数和白名单里的数是非大即小的关系，白名单中小于blacklist[low]的数有o（o<=k）个，说明whitelist[k]大于blacklist[low]，且小于blacklist[low+1]（若blacklist[low+1]存在），因为low是blacklist[i]-i<=k的上界，则blacklist[low+1]-low-1>k，此处说明blacklist[low+1]>blacklist[k]；若blacklist[low]-low>k，说明没走过low==mid的那条分支，low没有被改变过，low=0,说明i>0的所有f(i)都大于k,白名单里小于blacklist[0]的数有o(o>k)个，则blacklist[0]>k，0到k都在白名单中，k号元素即为k。

数组元素的随机翻转，数组大小为size,所有元素值为0,每次随机翻转一个元素值为0的元素为1。[4]用哈希表存储已被翻转的元素位置，不要用visited数组，visited数组会超出空间限制，且用哈希表时间复杂度也底鞋，速度更快。在0到total-1范围内随机选出一个索引k,则k坑位的元素要被翻转为1，total减1。如果map的键里有k，说明k坑位没有原来的k值，而因k早已被翻转，当时剩下的total-1个元素除去k反而还有个total-1号需要安家，就安在k坑位，此次选中k相当于选中total-1；如果map的键里没有k,说明k之前没有被选中，k坑位的元素是0,选中k即可。既然选完要选的，之后更新目前total（注意total已减一，跟选之前的total不相等）个值为0的索引，因为total在减少，抛去选中的k,total需要往前total的坑位里塞，如果map中的键有total,则map[k]=map[total]，map[total]还未被选中，随着total不在有效范围内，map[total]转移到k号坑位；如果map中的键没有total,total转移到k号坑位。

参考链接：[1].478. 在圆内随机生成点
 [2].398. 随机数索引
 [3].710. 黑名单中的随机数
 [4].519. 随机翻转矩阵

创建于2022.6.5/23.01，修改于2022.6.10/7.45