抱歉耽搁了，但我认为我有一个相对优雅的解决方案，包括O(n lg n)构建时间和O(lg n)获取随机元素时间。开始。
WeightedProbMap：
此类实现随机元素生成器。它是基于Iterable; 见Test.java下文。
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
class WeightedProbMap<EltType> {
private SortedMap<Integer, EltType> elts = new TreeMap<Integer, EltType>();
private Random rand = new Random();
private int sum = 0;
// assume: each weight is > 0; there is at least one element;
// elements should not be repeated
// ensure: this.elts maps cumulative weights to elements;
// this.sum is the total weight
public WeightedProbMap(Iterable<Pair<Integer, EltType>> weights) {
for (Pair<Integer, EltType> e : weights) {
this.elts.put(this.sum, e.second);
this.sum += e.first;
}
}
// assume: this was initialized properly (cf. constructor req)
// ensure: return an EltType with relative probability proportional
// to its associated weight
public EltType nextElt() {
int index = this.rand.nextInt(this.sum) + 1;
SortedMap<Integer, EltType> view = this.elts.headMap(index);
return view.get(view.lastKey());
}
}
Pair.java：只是一个简单的 Pair 类。
class Pair<X, Y> {
public Pair(X x, Y y) {
first = x;
second = y;
}
X first;
Y second;
}
Test.java：这是WeightedProbMap（WPM）类的一个非常简单的测试工具。我们构建一个具有相关权重的元素的 ArrayList，使用它来构建 WPM，然后从 WPM 中获取 10,000 个样本，以查看元素是否以预期的频率出现。
import java.util.ArrayList;
class Test {
public static void main(String argc[]) {
ArrayList<Pair<Integer, String> > elts = new ArrayList<Pair<Integer, String>>();
elts.add(new Pair<Integer, String>(20, "Hello"));
// elts.add(new Pair<Integer, String>(70, "World"));
// elts.add(new Pair<Integer, String>(10, "Ohai"));
WeightedProbMap<String> wpm = new WeightedProbMap<String>(elts);
for (int i = 0; i < 10000; ++i) {
System.out.println(wpm.nextElt());
}
}
}
测试这个：
elts.add(...)行Test.java。编译：
$ javac Pair.java WeightedProbMap.java Test.java
运行（例如，在 Unix 中）：
$ java Test | grep "Hello" | wc -l
这将为您提供该特定执行的计数。
解释：
构造函数：
（WeightedProbMapWPM）类使用 ajava.util.SortedMap将累积权重映射到元素。图形解释：
The constructor takes weights... ...and creates a mapping from the
3 +---+ number line:
| |
2 +---+ +---+ 2 0 2 5 7
| | | | +------+---------+------+
| | | | | X | Y | Z |
--+---+---+---+-- +------+---------+------+
X Y Z
nextElt()：
ASortedMap按键顺序存储其数据，这使其能够廉价地提供地图子集的“视图”。特别是，线
SortedMap<Integer, EltType> view = this.elts.headMap(index)
返回原始地图 ( this.elts) 的视图，其中仅包含严格小于 的键index。此操作 ( headMap) 是常数时间：构建view需要O(1)时间，如果您this.elts稍后要更改，更改也会反映在其中view。
一旦我们创建了view小于随机数的所有内容，我们现在只需找到该子集中的最大密钥。我们用 来做到这一点SortedMap.lastKey()，对于 来说，这TreeMap需要\Theta(lg n)时间。
为此，您必须缓存每个值 T 的相对频率。这为您提供了 O(n) 插入成本价格的 O(n) 概率分布（您必须更新每个 T 的相对频率每次插入时）。
如果您可以存储总和，那很容易做到：
只需将对 (T, int) 存储为类或普通数组中的任何内容，然后遍历它：
int val = Random.nextInt(total);
for (Pair p : pairs) {
val -= p.val;
if (val < 0) return p;
}
考虑到循环遍历 ArrayList 是遍历 n 个值的最有效方法，并且您显然不能比 O(n) 做得更好，因此不能变得更快。唯一的开销是 nextInt() 并且您在每个解决方案中也需要它（或类似的东西）。根据您组织 ArrayList 的方式（排序与否），其他操作会变得更便宜/更昂贵，但这对于该特定操作并不重要
编辑：虽然考虑到“你显然需要 O(n)”是不正确的。如果您很少更改数组中的值并且可以进行昂贵的准备并且内存不是问题，则可以通过存储 HashMap 做得更好。例如，如果您有一个分布： T0: 2 T1: 3 T2: 1
您可以在哈希图中插入 (0, T0), (1, T0), (2, T1),.,(4, T1), (5, T2)。
Edit2：或者查看 phooji 的方法，这对于更大的数据集应该是可行的。
构建一个逆映射，Map<Integer,T>使得每个键都是到目前为止处理的所有权重的总和。
例如，如果您有这张地图：
T1 -> 10
T2 -> 8
T3 -> 3
这个逆映射是：
10 -> T1
18 -> T2
21 -> T3
（为了获得更好的性能，您可以先按降序排列权重。）
然后生成一个介于0和所有权重之和之间的均匀分布的随机数，并在逆映射的key set中对这个数进行二分查找。
使用 arraylist 实际上会比使用 Map 更快，因为你可以在 O(1) 中完成它。
class RandVal<T> {
List<T> list = new ArrayList<T>();
Random rand = new Random();
public T randomValue() {
int next = rand.nextInt(list.size());
return list.get(next);
}
}
这是一件坏事的唯一方法是如果订单很重要（AABBAB vs ABBABA 或其他东西），但很明显它不是因为你使用的 Map 没有排序......
在这里。
我想出了一个优雅的解决方案！对于任何误解：我最初通过 ArrayList 中有多少个值来存储所有键的想法完全无视使用 Map 存储“使用整数的键的实例”的意义；任何类似的解决方案都会适得其反！假设地图是无序的，这是我的解决方案：
public T randomPick(Random r) {
int randomValue = r.nextInt(size());
int currentSum = 0;
T lastElement = null;
for (T t : map.keySet()){
if (randomValue < currentSum + map.get(t)){
return t;
}
currentSum+= map.get(t);
lastElement = t;
}
return lastElement;
}
它将 与 进行random value比较current sum + the current element's value。如果小于这个值，我们返回当前密钥。否则，继续前进并将该值添加到总和中。如果是这样的情况，即随机值永远不会小于任何值，我们返回lastElement.
希望这可以清除它。