384.打乱数组

[funnycoderstar]

题目描述

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

示例:

// 以数字集合 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();

思路

洗牌算法：
从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。

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

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

/**
 * Returns a random shuffling of the array.
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
    const { shuffleNums } = this;
    let current = shuffleNums.length - 1;
    while(current > -1) {
        // 生成一个范围在当前下标到数组末尾元素下标之间的随机整数
        const random = Math.floor(shuffleNums.length * Math.random());
        // 将当前元素和随机选出的下标所指的元素互相交换 
        [shuffleNums[current], shuffleNums[random]] = [shuffleNums[random], shuffleNums[current]];
        current--;
    }
    return shuffleNums;
};

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

• 时间复杂度： O(n)。Fisher-Yates 洗牌算法时间复杂度是线性的，因为算法中生成随机序列，交换两个元素这两种操作都是常数时间复杂度的。
• 空间复杂度： O(n)。因为要实现 重置，原始数组必须得保存一份。

拓展题目

实现随机抽奖程序 接受一个数组 arr, n , 从数组中抽出n个人

思路一：

按照我们正常的抽奖的最简单做法，一般是把工号写到一个球上面，摇 n 次，然后每次摇出1个号，该号码即为中奖号码，同时将该球拿出去，重复 n 次。

function lottery(arr, n) {
    const result = [];
    let i = 0;
    while( i < n) {
        // 每次从数组中随机抽出一个值，使用 slice将该值从原数组数组中删除，将该值添加到 result中
        const value = arr.splice(Math.floor(Math.random() * arr.length), 1)
        result.push(value[0]);
        i++;
    }
    return result;
}

思路二：

还有一种思路是将数组打乱，直接截取 前 n 个数。就是著名的 洗牌算法。

打乱数组（洗牌算法）：从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。

function disorder(array) {
    const length = array.length;
    let current = length - 1;
    while(current > -1) {
        const random = Math.floor(length * Math.random());
        // 数组的每个值都会和另外一个随机位置的值交换位置
        // 使用数组的解构赋值，交换数组中的两个元素的位置
        [ array[current], array[random] ] = [ array[random], array[current] ];
        current--;
    }
    return array;
}

const result = disorder(arr);
result.slice(0, n)

推荐阅读

• 神一样的随机算法
• JS中随机排列数组顺序（经典洗牌算法）和数组的排序方法
• leetcode官方题解