时间戳

首页 > 解决方案 > 随机播放数组编码挑战。难以理解某一部分

javascript - 随机播放数组编码挑战。难以理解某一部分

问题描述

问题：随机播放一组不重复的数字。

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 是否会自动撤回已使用的索引？

标签： javascript

解决方案

是的，Math.floor(Math.random() * n)表达式可以多次计算为相同的数字，但这没关系，因为随机数被用于，它将索引处的数字与所选随机索引处的swap数字切换。i

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

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是可信赖的）。

推荐阅读