随机排列数组/ 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)
预期时间算法。
谢谢。
你可能想看: