假设给了你一个范围和范围内的一些数字（例外情况）。现在您需要在该范围内生成一个随机数，除了给定的异常。
例如，如果range=[1..5]和exceptions={1，3，5}，则应该以相同的概率生成2或4。
我应该用什么逻辑来解决这个问题？
最佳答案
让我们假设，为了简单起见，数组的索引从1开始，范围从1到k不等当然，如果不是这样的话，你总是可以通过一个常数来改变结果。我们将调用异常数组ex_array，假设我们有c异常这些需要分类，这将在一段时间内变得相当重要。
现在，您只能使用k-e有用的数字，因此在1到k-e范围内找到一个随机数是有意义的。假设我们最终得到了数字r现在，我们只需要在数组中找到r-th有效数字。简单吗？没那么多。记住，您永远不能简单地以线性方式遍历任何数组，因为当您有很多数字时，这会减慢实现的速度。你已经做了一些二进制搜索，比如说，找到一个足够快的算法。
所以让我们试试更好的如果没有异常，r-th数字名义上应该位于原始数组的索引r处。当然，索引r处的数字是r，因为范围和数组索引从1开始但是，在1和r之间有一堆无效数字，您希望以某种方式获得r-th有效数字。因此，让我们对异常数组ex_array进行二进制搜索，找出有多少无效数字等于或小于r，因为这些无效数字位于1和r之间。如果这个数字是0，我们都完成了，但如果不是，我们还有更多的工作要做。
假设您在二进制搜索后发现n和1之间存在r无效数字让我们将数组中的n索引前进到索引r+n，并找到1和r+n之间的无效数字的数目，使用二进制搜索来查找ex_array中有多少元素小于或等于r+n如果这个数字正好是n，则不再遇到无效的数字，并且您已经找到了r-th有效的数字。否则，再次重复，这次是索引r+n'，其中n'是介于1和r+n之间的随机数。
重复这个步骤，直到您到达一个没有发现多余异常的阶段这里最重要的是，你永远不必以线性方式遍历任何数组您应该优化二进制搜索，使它们不总是从索引0开始假设您知道1和r之间有n个随机数不要从1开始下一个二进制搜索，而是从n中ex_array对应的索引之后的一个索引开始。
在最坏的情况下，您将对ex_array中的每个元素进行二进制搜索，这意味着您将执行c二进制搜索，从索引1的第一个开始，从索引2的下一个，等等，这给了您一个时间复杂度O(log(n!))。现在，Stirling's approximation告诉我们O(ln(x!)) = O(xln(x))，因此，如果c足够小以至于O(cln(c)) < O(k)，那么使用上述算法是有意义的，因为您可以使用从数组中提取有效元素的简单方法来实现O(k)复杂性。