随机化数组的有效方法 - 随机码

Question

我在接受采访时被问到这个问题而且我提供了各种解决方案,但面试官并不相信.我有兴趣找到解决方案.请提出你的看法:

问:编写一个有效的数据结构来实现ipod中的shuffle.它必须播放所有歌曲,每次以不同的随机顺序播放,同一首歌不应该重复.(主要是O(n))

一个解决方案,我在采访后想到了:我可以做一个随机的快速排序,没有递归.我们随机选择1个轴O(1)然后做快速排序O(n).现在歌曲将按某种顺序排序,然后我将它们播放到最后.一旦它到达终点,我将再次选择一个随机的枢轴,并一次又一次地重复这个过程.

此致,Sethu

Answer 1

你想要Fisher-Yates洗牌.请注意该页面上提到的实施错误,因为您当前接受的答案与一个错误相违背.

Answer 2

将所有歌曲放入一个数组中...对于数组中的每个元素，将其与随机位置交换。