随机排列数组/ n个数字的元素。可能的预期O(n)时间

您应该看一下Fisher- Yates混洗。

从文章:

正确实施了Fisher- Yates混洗是没有偏见的,因此每个排列的可能性都是相同的。该算法的现代版本也相当高效,只需要与洗牌项目的数量成正比的时间,而无需额外的存储空间。

因此它符合您的要求。这也很容易实现。

是否可以均匀地对n个大小的数组的元素进行混洗,即n个元素中任意一个的概率!在预期的O(n)时间内发生的组合是相同的。为何如此?我必须将元素洗牌A到一个新数组中B
当我尝试执行此操作时,我想到的第一件事就是选择一个i从1到n
的随机数,看看是否A[i]已被选择,如果是,则重复执行,否则放在A[i]的第一个可用位置B。但是,此优惠券收集器问题有预期的时间O(n log n)。有人可以建议一个O(n)预期时间算法。

谢谢。

你可能想看:
分享给朋友: