0

我有一个 Java 范围列表

public class Range {
   private int min, max;
   //constructor, getters, setters go here
}

所以，一个列表可能看起来像这样

ranges = [[3,9], [18,45], [90,112]]

我需要做以下功能

public int getRandomValueWithinRanges() {
   //returns a value which is contained inside a range inside the ranges ArrayList
}

我怎样才能做到这一点？这些范围内的每个值都应该有相同的被选择概率，并且应该有效地完成（即列出范围内的所有值，然后从该列表中随机选择是无效的）

4

3 回答 3

7

好吧，一种方法：

  1. 总结所有范围（即它们跨越的整数总数）

  2. 从中选择一个随机值[0-total)

  3. 把随机值当作一个索引，增量查找这个索引对应的范围

  4. 根据包含所述索引的范围开始偏移随机数..

于 2012-12-30T06:53:31.677 回答
1

首先，选择一个随机范围。然后从选定的随机范围中选择一个随机整数。

于 2012-12-30T07:24:00.820 回答
1

最佳解决方案取决于您是否可以将设置成本分摊到getRandomValueWithinRanges具有相同范围列表的多次调用中。

如果您无法摊销，那么@pst 的方法是最好的。

如果您可以摊销，那么有多种方法可以使该方法更快；例如

  • 构建所有范围元素的数组列表。这给出了最快的getRandom...，但有很大的设置时间和很大的空间开销。
  • 构建数据结构以加快随机索引（在@pst 的解决方案中）到值的映射。

应该注意的是，对随机范围和范围内的随机元素的简单选择很容易使随机数的选择产生偏差……除非您可以通过加权范围选择或其他方式弄清楚如何进行补偿。

于 2012-12-30T08:05:01.650 回答