algorithm - 不属于集合的等概率样本数

Question

我有一个数 n 和一组数 S ∈ [1..n]*，大小为 s(基本上是小于 n)。我想以等概率采样一个数 k ∈ [1..n]，但该数不允许在集合 S 中。

我试图在最坏的情况下解决问题 O(log n + s)。我不确定这是否可能。

一种天真的方法是创建一个从 1 到 n 的数字数组，不包括 S 中的所有数字，然后选择一个数组元素。这将在 O(n) 中运行并且不是一个选项。

另一种方法可能只是生成随机数 ∈[1..n] 并在它们包含在 S 中时拒绝它们。这没有理论上的限制，因为任何数字都可以被多次采样，即使它在集合中也是如此。但平均而言，如果 s 远小于 n，这可能是一个实用的解决方案。

Answer 1

假设 s 已排序。生成一个介于 1 和 n-s 之间的随机数，称之为 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,24,...,100] 是 6。二分查找发现 1 个元素最多为 3，所以我们递增到 4。现在我们比较 s 的下一个更大的元素，即 4，所以递增到 5 。重复此操作会发现 5 in，所以我们递增到 6。我们再次检查 s，发现 6 不在其中，所以我们停止。

例如，n = 100，s = {1,4,5,22}，我们的随机数是 4。所以我们的方法应该返回 [2,3,6,7,..., 21,23,24,...,100] 是 7。二分查找发现 2 个元素最多为 4，所以我们递增到 6。现在我们比较 s 的下一个更大的元素，即 5，所以递增到 7 . 我们再次检查 s，看到下一个数字 > 7，所以我们停止。

如果我们假设“s 远小于 n”意味着 |s| <= log(n)，那么我们将最多递增 log(n) 次，并且在任何情况下最多递增 s 次。

---

如果 s 未排序，那么我们可以执行以下操作。创建一个大小为 s 的位数组。生成 k。解析 s 并做两件事:1) 计算元素 < k 的数量，称此为 r。同时，如果 k+i 在 s 中，则将第 i 位设置为 1(索引为 0，因此如果 k 在 s 中，则设置第一个位)。

现在，递增 k 的次数等于 r 加上设置的位数是索引 <= 递增次数的数组。

例如，n = 100，s = {1,4,5,22}，我们的随机数是 4。所以我们的方法应该返回 [2,3,6,7,..., 21,23,24,...,100] 即 7。我们解析 s 和 1) 注意 1 个元素低于 4 (r=1)，并且 2) 将我们的数组设置为 [1, 1, 0, 0 ].我们对 r=1 增加一次，对两个设置位增加两次，最终为 7。

这是 O(s) 时间，O(s) 空间。