洗牌一个数组编码挑战。理解一部分有困难

Question

问题：对一组没有重复的数字进行乱序。

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

答：

 var Solution = function(nums) {

// hold nums in Solution

   this.nums = nums;
};

Solution.prototype.reset = function() {
   return this.nums;
};

Solution.prototype.shuffle = function() {

// create a copy of this.nums, shuffle it, and return it0

const shuffled = this.nums.slice();
const n = shuffled.length;
const swap = (arr, i, j) => {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// swap elements with random elements
for (let i = 0; i < n; i++) 
    swap(shuffled, i, Math.floor(Math.random() * n));

return shuffled;
};

我的问题：Math.floor（Math.random（）*n）你从数组的长度中得到一个随机索引。我不明白，这个代码不能重复吗？假设长度是3。公式不能得到2的索引和另一个2的索引，从而产生重复索引。有人能澄清一些我误解的事情吗？谢谢。Math.random自动撤回已经使用的索引吗？

Answer 1

Math.floor（Math.random（）*n）是的，它可以对相同的索引进行求值，但是这里您使用的是数字来交换元素，所以这是可以的。

Math.random会自动撤回已经使用过的索引吗？

不，你不需要跟踪以前生成的值

你能做的是用一个变量< code>object或< code>Map来跟踪先前添加的索引，如果随机生成的索引还没有被包括在那个变量中，则将其添加到最终输出中，否则再次生成一个新的索引，

但是在这种情况下并不需要。

Answer 2

是的，< code > math . floor(math . random()* n)表达式可以多次计算同一个数字，但这没关系，因为随机数在< code>swap中使用，它将索引< code>i处的数字与所选随机索引处的数字进行交换。

如果随机索引取自原始数组并添加到要返回的数组中，例如

const randIndex = Math.floor(Math.random() * n);
arrToBeReturned.push(arr[randIndex]);

你可能是对的，但这不是算法所做的。想象一下随机排序< code>[1，2，3]的数组:

循环的第一次迭代：i为0，选择的随机索引为2。交换指示0和2：

[3, 2, 1]

第二次迭代：i为1，所选随机索引为2。交换索引1和2：

[3, 1, 2]

第三次迭代:< code>i是2，选择的随机索引是2。互换指数2和2:

[3, 1, 2]

使用此代码，每个索引至少与另一个索引随机交换一次，确保到最后，数组是随机的，没有偏见（假设Math.random是值得信赖的）。