如何在少于 O(n) 的时间内在 std::set 中选择一个随机元素?
这个问题添加了约束.
我愿意允许不统一的选择，只要不偏向一边.
I'm willing to allow not-uniform selection as long as it's not to lop sided.
鉴于集合通常实现为二叉搜索树"，而我期望它们将包含某种用于平衡的深度或大小信息，我希望您可以对树进行某种加权随机游走.但是我不知道有任何远程便携的方式来做到这一点.
Given that "sets are typically implemented as binary search trees" and I expect they will contain some kind of depth or size information for balancing, I would expect you could do some sort of weighted random walk of the tree. However I don't know of any remotely portable way to do that.
约束不适用于摊销时间.
The constraint is NOT for the amortized time.
推荐答案
引入大小等于set的数组.使数组元素保存集合中每个元素的地址.生成以数组/集合大小为界的随机整数R，在R索引的数组元素中选取地址并取消引用以获得集合的元素.
Introduce array with size equal to set. Make array elements hold addresses of every element in set. Generate random integer R bounded by array/set size, pick address in array's element indexed by R and dereference it to obtain set's element.
相关文章