javascript - 打乱数组编码挑战。难以理解一部分

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) 表达式可以多次计算出相同的数字，但这没关系，因为 中使用了随机数swap，它将索引 i 处的数字与所选随机索引处的数字交换。

如果随机索引是从原始数组中取出并添加到要返回的数组中，eg

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

你是对的，但这不是算法正在做的事情。想象一下对 [1, 2, 3] 的数组进行随机排序:

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

[3, 2, 1]

第二次迭代:i 为 1，选择的随机索引为 2。交换索引 1 和 2:

[3, 1, 2]

第三次迭代:i 为 2，选择的随机索引为 2。交换索引 2 和 2:

[3, 1, 2]

使用这段代码，每个索引都与另一个索引随机交换至少一次，确保到最后，数组是无偏差随机化的(假设Math.random 值得信赖)。