3

我在一次面试中被问到这个问题，我给出了各种解决方案，但面试官并不相信。我有兴趣找到解决方案。请提出您的意见：

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

面试后我想到了一个解决方案：我可以在没有递归的情况下进行随机快速排序。我们随机选择 1 个枢轴 O(1)，然后进行快速排序 O(n)。现在歌曲将按某种顺序排序，我将它们播放到最后。一旦到达终点，我将再次选择一个随机枢轴，并一次又一次地重复此过程。

问候， 塞图

4

6 回答 6

8

你想要Fisher-Yates shuffle。请注意该页面上提到的实施错误，因为您当前接受的答案与其中一个错误。

于 2010-10-31T20:08:35.840 回答
5

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

于 2010-10-29T15:58:17.720 回答
1

好吧，我想到的第一个线性时间解决方案：

您可以制作所有歌曲的链接列表，这将花费大约 O(n)（假设插入是恒定时间操作）。然后，生成一个随机数，对列表的大小取模得到一个随机索引，然后删除该索引并将其附加到一个新列表中（两者都是常数时间操作）。

每个 O(n) 的插入 + 每个 O(n) 的删除 + 第二次插入 O(n)。这将总体上导致线性时间解决方案。

编辑：我完全忘记了走列表。因此，您可以将结果设为固定长度的数组。弹出链表的头部，为其分配随机索引，然后填充数组。

于 2010-10-29T16:03:07.890 回答
1

Nate 的（已编辑）和 Brian 的算法是 Fisher-Yates shuffle O(n)，而通过排序进行的shuffle 是 O(nlogn)，但实际上可能更快（http://en.wikipedia.org/wiki/Fisher% E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms）。弄错歌曲洗牌可能会产生微不足道的后果，但如果您正在为在线扑克游戏编写洗牌算法，请确保您知道自己在做什么（http://www.cigital.com/news/index.php?pg=艺术＆artid = 20）。

于 2010-10-29T20:08:38.703 回答
1

你想要的是Fisher-Yates Shuffle。这是java中的一个实现：

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

它的工作原理是将整个数组视为一顶帽子，并开始拉动随机元素并将它们排列在数组的前面。之后的所有元素i都在“桶中”，之前的所有元素i都被打乱了。

于 2018-05-16T01:33:24.047 回答
0

我是初学者，让我说一个想到的解决方案，如果有什么问题请告诉我。

让我们假设歌曲存储在单链表或双链表中。每次打开音乐播放器时，选择一个小于（您希望的任何数字）假设 k 的随机数，并反转列表中的每个 k 个节点，类似地执行两次或最多三次（如您所愿），这将花费 O( 2n) 或 O(3n) 时间洗牌。最后有一个指向列表最后一个节点的指针。每次听一首歌（访问一个节点）时，删除该节点并将其插入到最后一个节点旁边，这可以在 O(1) 时间内完成。这一直持续到音乐播放器关闭。

谢谢，急于知道答案的正确性。

于 2014-12-20T12:30:11.133 回答