A1m*_*A1m 4 algorithm probability
我有一个数字n和一组S ? [1..n]*大小的数字s(大大小于n).我想以k ? [1..n]相同的概率对数字进行采样,但不允许该数字在集合中S.
我试图在最坏的情况下解决问题O(log n + s).我不确定是否可能.
一种天真的方法是创建一个从1到n的数字数组,不包括所有数字S,然后选择一个数组元素.这将运行,O(n)不是一个选项.
另一种方法可能只是生成随机数?[1..n],如果包含它们则拒绝它们S.这没有理论上的约束,因为任何数字都可以被多次采样,即使它在集合中也是如此.但平均而言,这可能是一个实际的解决方案,如果s大大小于n.
说s是排序的.生成1到ns之间的随机数,称之为k.我们选择了{1,...,n} - s的第k个元素.现在我们需要找到它.
在s上使用二进制搜索来查找s <= k的元素的计数.这需要O(log | s |).将此添加到k.在这样做时,我们可能已经通过或者达到了s的其他元素.我们可以通过递增我们传递的每个这样的元素的答案来调整这个,我们通过从我们在二进制搜索中找到的点检查s的下一个更大的元素来找到它.
例如,n = 100,s = {1,4,5,22},我们的随机数是3.所以我们的方法应该返回[2,3,6,7,...,21,23]的第三个元素二进制搜索发现1个元素最多为3,所以我们增加到4.现在我们比较下一个更大的s元素,它是4,所以增量为5.重复这个找到5,所以我们增加到6.我们再次检查s,看到6不在其中,所以我们停止.
例如,n = 100,s = {1,4,5,22},我们的随机数是4.所以我们的方法应该返回[2,3,6,7,...,21,23]的第四个元素二进制搜索发现2个元素最多为4个,所以我们增加到6个.现在我们比较下一个更大的s元素,它是5,所以增量为7.我们检查一下,24,...,100,这是7.再一次,看到下一个数字是> 7,所以我们停下来.
如果我们假设"s基本上小于n"意味着| s | <= log(n),那么我们将最多增加log(n)次,并且在任何情况下最多增加s次.
如果s没有排序,那么我们可以执行以下操作.创建一个大小为s的位数组.生成k.解析并做两件事:1)计算元素的数量<k,称之为r.同时,如果k + i在s中,则将第i位设置为1(0如果索引,则如果k在s中则设置第一位).
现在,增加等于r的次数加上设定位数是具有索引<=增加次数的数组.
例如,n = 100,s = {1,4,5,22},我们的随机数是4.所以我们的方法应该返回[2,3,6,7,...,21,23]的第四个元素我们解析s和1)注意1个元素低于4(r = 1),2)将我们的数组设置为[1,1,0,0].,24,...,100].我们为r = 1递增一次,对于两个设置位再递增两次,最后为7.
这是O(s)时间,O(s)空间.