algorithm - 在给定范围内查找随机数，排除某些可能的数字

Question

假设给定了一个范围和范围内的一些数字(异常(exception))。现在您需要在给定的 exceptions except 范围内生成一个随机数。

例如，如果 range = [1..5] 且 exceptions = {1, 3, 5}，您应该以相等的概率生成 2 或 4。

我应该用什么逻辑来解决这个问题？

Answer 1

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

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