Medium

题目描述

给定一个整数数组 nums，设计算法来随机打乱这个数组。数组的所有排列应该是等概率的。

实现 Solution 类：

  • 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^6 <= nums[i] <= 10^6
  • nums 中的所有元素都是唯一的
  • 最多会对 reset 和 shuffle 进行 10^4 次调用

解题思路

这道题需要设计一个能够随机打乱数组的数据结构，核心在于实现真正随机的洗牌算法。

主要思路是使用 Fisher-Yates 洗牌算法（也称为 Knuth 洗牌算法），这是公认的最佳洗牌算法，能保证所有排列出现的概率相等。

算法原理：

  1. 从数组末尾开始，依次向前遍历
  2. 对于每个位置 i，从 [0, i] 范围内随机选择一个索引 j
  3. 交换 nums[i] 和 nums[j] 的值
  4. 继续向前遍历直到数组开头

这样做的正确性在于：第 i 个位置的元素有 1/(i+1) 的概率被选中留在当前位置，有 i/(i+1) 的概率被交换到前面的位置。数学上可以证明这样产生的每个排列概率都是 1/n!。

实现要点：

  • 构造函数中保存原始数组的副本
  • reset() 方法返回原始数组
  • shuffle() 方法先复制原始数组，然后应用 Fisher-Yates 算法

时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
private:
    vector<int> original;
    
public:
    Solution(vector<int>& nums) {
        original = nums;
    }
    
    vector<int> reset() {
        return original;
    }
    
    vector<int> shuffle() {
        vector<int> result = original;
        for (int i = result.size() - 1; i > 0; i--) {
            int j = rand() % (i + 1);
            swap(result[i], result[j]);
        }
        return result;
    }
};

class Solution:

    def __init__(self, nums: List[int]):
        self.original = nums[:]
        
    def reset(self) -> List[int]:
        return self.original
        
    def shuffle(self) -> List[int]:
        result = self.original[:]
        for i in range(len(result) - 1, 0, -1):
            j = random.randint(0, i)
            result[i], result[j] = result[j], result[i]
        return result

public class Solution {
    private int[] original;
    private Random random;

    public Solution(int[] nums) {
        original = new int[nums.Length];
        Array.Copy(nums, original, nums.Length);
        random = new Random();
    }
    
    public int[] Reset() {
        return (int[])original.Clone();
    }
    
    public int[] Shuffle() {
        int[] result = (int[])original.Clone();
        for (int i = result.Length - 1; i > 0; i--) {
            int j = random.Next(0, i + 1);
            int temp = result[i];
            result[i] = result[j];
            result[j] = temp;
        }
        return result;
    }
}

var Solution = function(nums) {
    this.original = [...nums];
};

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

Solution.prototype.shuffle = function() {
    let result = [...this.original];
    for (let i = result.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        [result[i], result[j]] = [result[j], result[i]];
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(n)O(n)
reset()O(1) 或 O(n)O(1) 或 O(n)
shuffle()O(n)O(n)

说明：

  • 构造函数需要复制原数组，时间和空间复杂度都是 O(n)
  • reset() 的复杂度取决于是否需要返回新数组，返回引用是 O(1)，返回副本是 O(n)
  • shuffle() 使用 Fisher-Yates 算法，需要遍历数组一次，时间复杂度 O(n)，需要创建结果数组副本，空间复杂度 O(n)