leetcode384：打乱数组（洗牌算法）

[sisterAn]

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

附赠leetcode可测试链接：leetcode384：打乱数组

[7777sea]

浅拷贝数组，利用random()方法重制数组角标

/**
 * @param {number[]} nums
 */
var Solution = function(nums) {
 this.nums = nums;
};

/**
 * Resets the array to its original configuration and return it.
 * @return {number[]}
 */
Solution.prototype.reset = function() {
 return this.nums;
};

/**
 * Returns a random shuffling of the array.
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
 let num = this.nums.slice();
 
 for(let i = 0;i < num.length;i++){
 let index = Math.floor((i+1)* Math.random());
 [num[index],num[i]] = [num[i],num[index]]
 
 }
 return num;
};

[xyj626553989]

function solution(arr) {
 let tempArr = arr.slice()
 for (let i = 0; i < tempArr.length; i++) {
 let index = Math.floor(Math.random() * (tempArr.length - i) + i)
 let temp = tempArr[i]
 tempArr[i] = tempArr[index]
 tempArr[index] = temp
 }
 return tempArr
}```

[Cxy56]

sort(() => Math.random() - 0.5)
sort() 会根据 compareFunction(a, b) 的返回值，来决定 a 和 b 的相对位置：
如果 compareFunction(a, b) 小于 0 ，那么 a 会被排列到 b 之前；
如果 compareFunction(a, b) 大于 0 ，那么 b 会被排列到 a 之前；
如果 compareFunction(a, b) 等于 0 ， a 和 b 的相对位置不变（不稳定！）

真正乱排序：
最后一位开始往前遍历。每次循环生成随机数：
math.random()*(i+1) , 向下取整，然后两个位置元素交换；
实现真正的乱序

/**
 * @param {number[]} nums
 */
var Solution = function(nums) {
 this.origin = nums

};

/**
 * Resets the array to its original configuration and return it.
 * @return {number[]}
 */
Solution.prototype.reset = function() {
 return this.origin

};

/**
 * Returns a random shuffling of the array.
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
 let copyArr = [...this.origin];
 let len = copyArr.length;
 for(let i = len - 1; i >=0; i-- ) {
 let index = ~~(Math.random() * (i+1));
 [copyArr[index], copyArr[i]] = [copyArr[i], copyArr[index]];
 }
 return copyArr;
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.reset()
 * var param_2 = obj.shuffle()
 */

[syc666]

function fun(arr){
 const res = []
 while(arr.length){
 let index = Math.floor(Math.random()*arr.length)
 res.push(arr.splice(index,1)[0])
 }
 return res
}

[sisterAn]

解答：Fisher-Yates 洗牌算法

let Solution = function(nums) {
 this.nums = nums
};

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

Solution.prototype.shuffle = function() {
 let res = [...this.nums]
 let n = res.length
 for(let i = n-1; i >= 0; i--) {
 let randIndex = Math.floor(Math.random() * (i + 1))
 swap(res, randIndex, i)
 }
 return res
};

let swap = function(arr, i, j) {
 const temp = arr[i]
 arr[i] = arr[j]
 arr[j] = temp
}

复杂度分析：

• 时间复杂度： O(n)
• 空间复杂度：O(n)，需要实现 reset 功能，原始数组必须得保存一份

[AnranS]

var Solution = function(nums) {
 this.arr = nums;
};

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

Solution.prototype.shuffle = function() {
 // 拷贝数组
 let nums = this.arr.slice();
 let len = nums.length;
 for(let i = 0;i<len;i++) {
 let ran = Math.random()*len | 0;
 [nums[i], nums[ran]] = [nums[ran], nums[i]];
 }
 return nums;
};

[XW666]

 function shuffle(arr) {
 let len = arr.length;
 let i, t;
 while (len) {
 // /随机索引值i是从0-arr.length中随机抽取的
 i = Math.floor(Math.random() * (len--))
 //把从数组中随机抽取到的值与当前遍历的值互换位置
 t = arr[len]
 arr[len] = arr[i];
 arr[i] = t
 }
 return arr
 }