384. 打乱数组

题目描述

输入一个元素互不相同的整数数组 nums。实现类 Solution，用来随机打乱这个数组：

Solution(nums)：用 nums 创建对象。reset()：把数组恢复成最初的顺序并返回它。shuffle()：返回随机打乱后的数组。

打乱必须公平：长度为 n 的数组共有 n! 种排列，每种排列被返回的概率都要相等。

示例中第一行为方法名，第二行为参数，构造函数的返回记为 null。

示例 1

输入：操作 = ["Solution","shuffle","reset","shuffle"], 参数 = [[[1,2,3]],[],[],[]]
输出：[null,[1,2,3],[1,2,3],[1,2,3]]

解释：shuffle() 返回 [1,2,3] 的任意排列都可以，这次运行两次都恰好得到 [1,2,3]；reset() 总是返回 [1,2,3]。

数据范围

1 <= nums.length <= 50
-10^6 <= nums[i] <= 10^6
nums 中元素互不相同
reset 和 shuffle 合计最多调用 10^4 次

解题思路：Fisher-Yates 洗牌

用 Fisher-Yates 洗牌：从最后一个位置 i 开始往前，每次在 [0, i] 中等概率选一个下标 j，交换 a[i] 与 a[j]，然后 a[i] 就不再变动。每一步的选择数依次是 n、n-1、…、2，总共 n! 种选择序列，恰好一一对应 n! 个排列，所以每个排列的概率都是 1/n!。另存一份 orig，reset 时复制回来即可。

为什么正确

处理到位置 i 时，下标大于 i 的位置已经锁定；还没放置的元素都在 [0, i] 中，每个都有 1/(i+1) 的机会被放到位置 i。

复杂度分析

shuffle 时间 O(n)，reset 时间 O(n)；空间 O(n)（保存原数组）。

易错点

把 j 的范围写成 [0, n-1]（每步都在整个数组里随便选）或 [0, i-1]（不允许留在原位），都会让某些排列概率偏高或根本取不到；另外 reset 要复制 orig，不能让 cur 直接引用 orig，否则下一次 shuffle 会改坏原数组。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def __init__(self, nums: List[int] = ()):
        self.orig = list(nums)
        self.cur = list(nums)

    def reset(self) -> List[int]:
        self.cur = self.orig[:]
        return self.cur

    def shuffle(self) -> List[int]:
        a = self.cur
        for i in range(len(a) - 1, 0, -1):
            j = random.randint(0, i)
            a[i], a[j] = a[j], a[i]
        return a

class Solution {
    private int[] orig;
    private int[] cur;
    private java.util.Random rng = new java.util.Random();

    public Solution(int[] nums) {
        orig = nums.clone();
        cur = nums.clone();
    }

    public int[] reset() {
        cur = orig.clone();
        return cur;
    }

    public int[] shuffle() {
        int[] a = cur;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rng.nextInt(i + 1);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        return a;
    }
}

class Solution {
    vector<int> orig;
    vector<int> cur;
    mt19937 rng{random_device{}()};
public:
    Solution(vector<int>& nums) {
        orig = nums;
        cur = nums;
    }

    vector<int> reset() {
        cur = orig;
        return cur;
    }

    vector<int> shuffle() {
        vector<int>& a = cur;
        for (int i = (int)a.size() - 1; i > 0; i--) {
            int j = uniform_int_distribution<int>(0, i)(rng);
            swap(a[i], a[j]);
        }
        return a;
    }
};

type Solution struct {
	orig []int
	cur  []int
}

func Constructor(nums []int) Solution {
	orig := append([]int{}, nums...)
	cur := append([]int{}, nums...)
	return Solution{orig, cur}
}

func (this *Solution) Reset() []int {
	this.cur = append([]int{}, this.orig...)
	return this.cur
}

func (this *Solution) Shuffle() []int {
	a := this.cur
	for i := len(a) - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		a[i], a[j] = a[j], a[i]
	}
	return a
}

var Solution = function(nums) {
    this.orig = nums.slice();
    this.cur = nums.slice();
};

Solution.prototype.reset = function() {
    this.cur = this.orig.slice();
    return this.cur;
};

Solution.prototype.shuffle = function() {
    const a = this.cur;
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
};

class Solution {
    orig: number[];
    cur: number[];

    constructor(nums: number[]) {
        this.orig = nums.slice();
        this.cur = nums.slice();
    }

    reset(): number[] {
        this.cur = this.orig.slice();
        return this.cur;
    }

    shuffle(): number[] {
        const a = this.cur;
        for (let i = a.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [a[i], a[j]] = [a[j], a[i]];
        }
        return a;
    }
}

载入编辑器，自己跑一遍 →

其他解法

两种方法都生成均匀随机排列：暴力抽取每次删除代价 O(n)；Fisher-Yates 把“已抽取区”和“待选区”放在同一数组两端，用交换代替删除，降到 O(n)。

解法 2：暴力抽取时间 O(n²)，空间 O(n)

把当前数组复制到待选列表 waiting。依次确定第 0、1、…、n-1 个位置：在 waiting 中随机选一个下标，把该元素放到当前位置，再从 waiting 中删除它。每个元素被放到每个位置的概率都是 1/n。

最贴近“从帽子里依次抽签”的直觉，容易证明等概率。每次从列表中删除元素要 O(n)，整体 O(n²)，还需要额外列表；Fisher-Yates 在原数组上交换，O(n) 且不需额外空间。

class Solution:
    def __init__(self, nums: List[int] = ()):
        self.orig = list(nums)
        self.cur = list(nums)

    def reset(self) -> List[int]:
        self.cur = self.orig[:]
        return self.cur

    def shuffle(self) -> List[int]:
        waiting = self.cur[:]
        for i in range(len(self.cur)):
            j = random.randrange(len(waiting))
            self.cur[i] = waiting.pop(j)
        return self.cur

class Solution {
    private int[] orig;
    private int[] cur;
    private java.util.Random rng = new java.util.Random();

    public Solution(int[] nums) {
        orig = nums.clone();
        cur = nums.clone();
    }

    public int[] reset() {
        cur = orig.clone();
        return cur;
    }

    public int[] shuffle() {
        List<Integer> waiting = new ArrayList<>();
        for (int x : cur) waiting.add(x);
        for (int i = 0; i < cur.length; i++) {
            int j = rng.nextInt(waiting.size());
            cur[i] = waiting.remove(j);
        }
        return cur;
    }
}

class Solution {
    vector<int> orig;
    vector<int> cur;
    mt19937 rng{random_device{}()};
public:
    Solution(vector<int>& nums) {
        orig = nums;
        cur = nums;
    }

    vector<int> reset() {
        cur = orig;
        return cur;
    }

    vector<int> shuffle() {
        vector<int> waiting = cur;
        for (int i = 0; i < (int)cur.size(); i++) {
            int j = uniform_int_distribution<int>(0, (int)waiting.size() - 1)(rng);
            cur[i] = waiting[j];
            waiting.erase(waiting.begin() + j);
        }
        return cur;
    }
};

type Solution struct {
	orig []int
	cur  []int
}

func Constructor(nums []int) Solution {
	orig := append([]int{}, nums...)
	cur := append([]int{}, nums...)
	return Solution{orig, cur}
}

func (this *Solution) Reset() []int {
	this.cur = append([]int{}, this.orig...)
	return this.cur
}

func (this *Solution) Shuffle() []int {
	waiting := append([]int{}, this.cur...)
	for i := range this.cur {
		j := rand.Intn(len(waiting))
		this.cur[i] = waiting[j]
		waiting = append(waiting[:j], waiting[j+1:]...)
	}
	return this.cur
}

var Solution = function(nums) {
    this.orig = nums.slice();
    this.cur = nums.slice();
};

Solution.prototype.reset = function() {
    this.cur = this.orig.slice();
    return this.cur;
};

Solution.prototype.shuffle = function() {
    const waiting = this.cur.slice();
    for (let i = 0; i < this.cur.length; i++) {
        const j = Math.floor(Math.random() * waiting.length);
        this.cur[i] = waiting.splice(j, 1)[0];
    }
    return this.cur;
};

class Solution {
    orig: number[];
    cur: number[];

    constructor(nums: number[]) {
        this.orig = nums.slice();
        this.cur = nums.slice();
    }

    reset(): number[] {
        this.cur = this.orig.slice();
        return this.cur;
    }

    shuffle(): number[] {
        const waiting = this.cur.slice();
        for (let i = 0; i < this.cur.length; i++) {
            const j = Math.floor(Math.random() * waiting.length);
            this.cur[i] = waiting.splice(j, 1)[0];
        }
        return this.cur;
    }
}

设计专题的其他题目

查看设计全部题目 →