1

Suppose you are given a range and a few numbers in the range (exceptions). Now you need to generate a random number in the range except the given exceptions.

For example, if range = [1..5] and exceptions = {1, 3, 5} you should generate either 2 or 4 with equal probability.

What logic should I use to solve this problem?

4

7 回答 7

5

如果您根本没有约束，我想这是最简单的方法：创建一个包含有效值的数组，a[0]...a[m]. 返回a[rand(0,...,m)]。

如果不想创建辅助数组，但可以统计异常个数e和原始范围内的元素个数，n可以简单生成一个随机数r=rand(0 ... n-e)，然后用不打勾的计数器找到有效元素在异常情况下，当它等于 时停止r。

于 2013-09-13T19:34:51.630 回答
4

取决于案件的具体情况。对于您的具体示例，如果 Uniform(0,1) 低于 1/2，我将返回 2，否则返回 4。同样，如果我看到诸如“例外是奇数”之类的模式，我会生成范围的一半和两倍的值。不过，一般来说，我会生成范围内的数字，检查它们是否在异常集中，如果它们在，则拒绝并重试 - 出于显而易见的原因，这种技术称为接受/拒绝。有多种技术可以提高异常列表检查的效率，具体取决于它的大小以及它可能具有的模式。

于 2013-09-13T19:35:52.420 回答
2

在 Python 中，解决方案非常简单（给定您的示例）：

import random 
rng = set(range(1, 6))
ex = {1, 3, 5}
random.choice(list(rng-ex))

要优化解决方案，需要知道范围有多长以及有多少异常。如果异常的数量非常少，则可以从该范围内生成一个数字，然后检查它是否不是异常。如果异常的数量占主导地位，那么将剩余的数字收集到一个数组中并生成随机索引以获取非异常可能是有意义的。

在这个答案中，我假设知道如何从一个范围内获取一个整数随机数。

于 2013-09-13T19:47:18.883 回答
2

让我们假设，为简单起见，数组的索引从 开始1，并且您的范围从1到k。当然，如果不是这种情况，您总是可以将结果移动一个常数。我们将调用异常数组，ex_array假设我们有c异常。这些需要排序，这将在一段时间内变得非常重要。

现在，您只有k-e有用的数字可以使用，因此在 to 范围内找到一个随机数将是有意义1的k-e。假设我们以数字结尾r。现在，我们只需要在您的数组中找到r-th 有效数字。简单的？没那么多。请记住，您永远不能简单地以线性方式遍历任何数组，因为当您有很多数字时，这确实会减慢您的实现速度。例如，您必须进行某种二进制搜索以提出足够快的算法。

所以让我们尝试一些更好的东西。如果您没有例外，该r-th数字名义上会位于原始数组中的索引处。rindexr处的数字r当然是 ，因为您的范围和数组索引从1. 1但是，您在和之间有一堆无效数字r，并且您想以某种方式获得r-th 有效数字。因此，让我们对异常数组 进行二分搜索ex_array，以找出有多少无效数等于或小于 r，因为我们有很多无效数位于1和之间r。如果这个数字是0，我们就完成了，但如果不是，我们还有更多工作要做。

假设您发现在二分查找之间和之后存在n无效数字。让我们将数组中的索引推进到索引，并找到位于和之间的无效数字的数量，使用二进制搜索来查找其中有多少个元素小于或等于。如果这个数字恰好是，则不再遇到无效数字，并且您已经找到了有效数字。否则，再次重复，这次是索引，其中是介于和之间的随机数的数量。1r nr+n1r+nex_arrayr+nnr-thr+n'n'1r+n

重复直到你到达没有发现多余异常的阶段。这里重要的是，您永远不必以线性方式走过任何阵列。您应该优化二进制搜索，使它们不总是从 index 开始0。假设你知道1和之间有 n 个随机数r。您可以从与in1对应的索引之后的一个索引开始，而不是从 开始下一个二进制搜索。nex_array

在最坏的情况下，您将对 中的每个元素进行二分搜索ex_array，这意味着您将进行c二分搜索，第一个从 index 开始1，下一个从 index开始2，依此类推，时间复杂度为O(log(n!)). 现在，斯特林的近似值告诉我们O(ln(x!)) = O(xln(x))，所以使用上面的算法只有在c足够小时才有意义 ，因为您可以使用首先从数组中提取有效元素的简单方法O(cln(c)) < O(k)来实现复杂性。O(k)

于 2013-09-13T19:52:26.197 回答
1

假设初始范围是 [1,n] 并且排除集的大小是 x。首先生成一个从 [1, nx] 到数字 [1,n] 的映射，不包括排除集中的数字。此映射为 1-1，因为两边的数字相等。在问题中给出的示例中，映射如下 - {1->2,2->4}。

另一个例子假设列表是 [1,10] 并且排除列表是 [2,5,8,9] 那么映射是 {1->1, 2->3, 3->4, 4->6, 5->7、6->10}。该映射可以在 O(nlogn) 的最坏情况时间复杂度下创建。

现在生成一个介于 [1, nx] 之间的随机数，并使用映射将其映射到相应的数字。地图外观可以在 O(logn) 中完成。

于 2015-01-23T17:11:33.653 回答
1

这是另一种方法……继续生成随机数，直到你得到一个未被排除的随机数。

假设您想要的范围是 [0,100)，不包括 25,50 和 75。

将排除的值放在哈希表或位数组中以进行快速查找。

int randNum = rand(0,100);

while( excludedValues.contains(randNum) )
{
    randNum = rand(0,100);
}

复杂性分析更加困难，因为潜在的 rand(0,100) 每次都可能返回 25、50 或 75。但是，即使排除了一半范围，这也不太可能（假设是随机数生成器）。

在上述情况下，我们只为原始值的 3/100 重新生成随机值。

所以 3% 的时间你再生一次。在这 3% 中，只有 3% 需要再生，等等。

于 2013-09-20T05:58:47.473 回答
0

如果你有枚举器或集合操作，你可以用一种通用的方式来做。例如使用 Linq：

void Main()
{
    var exceptions = new[] { 1,3,5 };
    RandomSequence(1,5).Where(n=>!exceptions.Contains(n))
                       .Take(10)
                       .Select(Console.WriteLine);
}

static Random r = new Random();

IEnumerable<int> RandomSequence(int min, int max)
{
    yield return r.Next(min, max+1);
}

我想感谢一些现已删除的评论：

  • 该程序可能永远不会结束（仅在理论上），因为可能存在一个从不包含有效值的序列。有道理。我认为这是可以向面试官解释的，但是我相信我的例子对于上下文来说已经足够好了。

  • 分配是公平的，因为每个元素都有相同的机会出现。

  • 以这种方式回答的好处是你表现出对现代“函数式”编程的理解，这对面试官来说可能很有趣。

  • 其他答案也是正确的。这是对这个问题的不同看法。

于 2013-09-13T20:03:30.353 回答