LeetCode 第384题：打乱数组

📖 文章摘要

本文详细解析LeetCode第384题“打乱数组”，这是一道设计题。文章提供了基于Fisher-Yates洗牌算法的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升算法设计能力的读者。

核心知识点： 设计、随机化、洗牌算法 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升算法设计能力的程序员

题目描述

给你一个整数数组 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 <= 200
• -10^6 <= nums[i] <= 10^6
• nums 中的所有元素都是 唯一的
• 最多可以调用 5 * 10^4 次 reset 和 shuffle

解题思路

本题可以使用Fisher-Yates洗牌算法解决：

1. 保存原始数组
2. 实现reset方法返回原始数组
3. 实现shuffle方法使用Fisher-Yates算法打乱数组

时间复杂度： O(n) shuffle操作 空间复杂度： O(n)

图解思路

Fisher-Yates洗牌算法

步骤	操作	说明
1	从后向前遍历	选择当前位置
2	随机选择前面的位置	交换元素
3	重复直到完成	保证随机性

操作流程

操作	步骤	说明
reset	返回原始数组	恢复初始状态
shuffle	使用Fisher-Yates算法	随机打乱数组

代码实现

C# 实现

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

Python 实现

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

C++ 实现

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

执行结果

C# 实现

• 执行用时：92 ms
• 内存消耗：24.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：13.2 MB

C++ 实现

• 执行用时：4 ms
• 内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用Fisher-Yates洗牌算法保证随机性
2. 💡 空间复杂度优化
3. 🔍 处理边界情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未使用Fisher-Yates算法
2. 🚫 随机性保证不足
3. 🚫 边界条件处理错误
4. 🚫 空间复杂度优化不足

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
Fisher-Yates	O(n)	O(n)	随机性好	需要额外空间
排序	O(n log n)	O(n)	简单	随机性差

相关题目

• LeetCode 215. 数组中的第K个最大元素 - 中等
• LeetCode 347. 前 K 个高频元素 - 中等
• LeetCode 973. 最接近原点的 K 个点 - 中等

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第384题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！