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

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

示例:

// 以数字集合 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：打乱数组

浅拷贝数组，利用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;
};

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
}```

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()
 */

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
}

解答：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 功能，原始数组必须得保存一份

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;
};

 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
  }

Navigation Menu

Repository navigation

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

解答：Fisher-Yates 洗牌算法

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

7777sea commented on Jul 1, 2020

xyj626553989 commented on Jul 1, 2020

Cxy56 commented on Jul 1, 2020

syc666 commented on Jul 1, 2020

sisterAn commented on Jul 2, 2020

解答：Fisher-Yates 洗牌算法

AnranS commented on Nov 20, 2020

XW666 commented on Mar 1, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions