LeetCode|384. 打乱数组(day22)

作者：MJ昊

博客：掘金、CSDN等

公众号：程序猿的编程之路

今天是 昊 的算法之路第22天，今天分享的是LeetCode第384题打乱数组的解题思路。这是一道中等难度的题目，要求我们实现一个算法，使得数组支持随机打乱和重置为初始顺序的功能，并且每种排列出现的概率应当相等。

题目描述简要回顾

LeetCode 第 384 题要求我们实现一个算法，使给定的数组支持随机打乱和重置为初始顺序的功能。打乱操作需要保证每个排列出现的概率是均等的。

解题思路

我们可以通过Fisher-Yates洗牌算法 实现打乱操作。这种算法从后向前遍历数组，每次随机选择一个位置并交换元素，确保所有排列出现的概率相等。重置操作则是直接返回初始数组。

代码实现：

var Solution = function (nums) {
    this.nums = [...nums]; // 存储原始数组
};

Solution.prototype.reset = function () {
    return this.nums; // 返回原始数组
};

Solution.prototype.shuffle = function () {
    const res = [...this.nums]; // 创建数组副本
    for (let i = res.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1)); // 在 [0, i] 范围内随机选择
        [res[i], res[j]] = [res[j], res[i]]; // 交换元素
    }
    return res;
};

复杂度分析

• 时间复杂度：
  • reset()：O(1)，直接返回原始数组。
  • shuffle()：O(n)，需要遍历数组进行元素交换。
• 空间复杂度：
  O(n)，由于存储了数组副本。

总结

这道题考察了如何实现洗牌算法，并且要求保证洗牌后每种排列出现的概率均等。通过 Fisher-Yates 算法 ，我们可以在 O(n) 时间内完成打乱操作，满足题目要求。
这种算法在实际开发中非常常用，比如在实现随机抽样、随机排序等功能时。