What is the main idea behind Shuffle an Array?

The main idea is to create a Solution class that can shuffle an array randomly while allowing it to be reset to its original order.

Why is Fisher-Yates recommended for this problem?

Fisher-Yates guarantees each permutation of the array occurs with equal probability, avoiding bias that arises from naive shuffling methods.

How should multiple shuffle calls be handled?

Always start shuffle from a copy of the original array to ensure uniform randomness across repeated calls, preventing cumulative bias.

Can this approach work for arrays with negative numbers?

Yes, the algorithm works for any integer values within the array, as randomness is independent of the numeric values.

What pattern does this problem demonstrate?

It exemplifies the Array plus Math pattern, combining array manipulation with probability principles to ensure unbiased permutations.

#384

Medium

auto_awesome数组·数学

LeetCode 题解工作台

打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是等可能的。实现 Solution class: Solution(int[] nums) 使用整数数组 nums 初始化对象 int[] reset() 重设数组到它的初始状态并返回 int[] s…

数组数学设计随机化

题目描述

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

1 <= nums.length <= 50
-10⁶ <= nums[i] <= 10⁶
nums 中的所有元素都是 唯一的
最多可以调用 10⁴ 次 reset 和 shuffle

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums.copy()

    def reset(self) -> List[int]:
        self.nums = self.original.copy()
        return self.nums

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


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

speed

复杂度分析

指标	值
时间	complexity for shuffle is O(n) per call, and reset is O(n) for copying. Space complexity is O(n) for storing the original array copy, ensuring repeated shuffles do not accumulate errors.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about unbiased shuffling of arrays.
question_mark
Checks if Fisher-Yates is implemented correctly to ensure uniform permutations.
question_mark
Verifies handling multiple shuffle and reset calls efficiently.

warning

常见陷阱

外企场景

error
Modifying the array in place without preserving the original leads to biased shuffles.
error
Using naive random swaps can produce non-uniform distributions.
error
Failing to handle multiple consecutive shuffle calls from the same modified array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Shuffle a linked list maintaining equal probability for all node permutations.
arrow_right_alt
Shuffle a multidimensional array along one axis uniformly.
arrow_right_alt
Implement a weighted shuffle where each element has a different selection probability.

help

常见问题

外企场景

继续练习

#381 O(1) 时间插入、删除和获取随机元素 - 允许重复 #380 O(1) 时间插入、删除和获取随机元素 #497 非重叠矩形中的随机点