一个有效的方法来随机化一个数组 - 随机码 [英] An Efficient way of randomizing an array - Shuffle code

问题描述

我在接受采访时被问到这个问题，我提供了各种解决方案，但面试官不信服。我有兴趣找到一个解决方案。请扔您的意见：

I was asked this question in an interview and I gave various solutions but the interviewer was not convinced. I am interested to find a solution. Please throw in your views :

Q：编写一个有效的数据结构来实现在iPod中的随机播放。它必须播放所有的歌曲，每次以不同的随机顺序，同一首歌曲不应该重复。 （大多数是O（n））

Q: Write an efficient data structure to implement the shuffle in an ipod. It must play all the songs, each time in different random order, the same song should not be repeated. ( mostly O(n))

一个解决方案，我在采访后想到：我可以做一个随机的快速排序而不递归。在我们随机的地方，选择1个O（1），然后进行快速排序O（n）。现在歌曲将按照一些顺序进行排序，我玩到最后。一旦达到目的，我将再次选择一个随机的枢纽，并重复这个过程一次又一次。

One solution , I thought off after the interview : I can do a randomized quick sort without recursion. Where we randomly, chose 1 pivot O(1) and then do quicksort O(n). Now songs will be sorted in some order and I play them till the end. Once it reaches the end, I will Again chose a random pivot and , repeat this process again and again.

Regards，
Sethu

Regards, Sethu

推荐答案

数组中的歌曲...
阵列中的每个元素都以随机位置交换。

Place all the songs in an array... For each element in the array swap it with a random position.

这篇关于一个有效的方法来随机化一个数组 - 随机码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！