如何在少于 O(n) 的时间内在 std::set 中选择一个随机元素?

How to select a random element in std::set in less than O(n) time?(如何在少于 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.

这篇关于如何在少于 O(n) 的时间内在 std::set 中选择一个随机元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！