LeetCode 384 打乱数组

文章目录

• 摘要
• 描述
• 题解答案
• 题解代码分析
  • 1. 数据结构的设计
  • 2. 为什么需要两个数组？
  • 3. init() 方法详解
  • 4. reset() 方法详解
  • 5. shuffle() 方法详解
  • 6. Fisher-Yates 洗牌算法详解
  • 7. Swift 中的 stride 函数
  • 8. swapAt() 方法
  • 9. 边界情况处理
• 示例测试及结果
  • 示例 1：基本操作
  • 示例 2：题目示例
  • 示例 3：单元素数组
  • 示例 4：验证随机性
  • 示例 5：多次 reset 和 shuffle
• 时间复杂度
• 空间复杂度
• 实际应用场景
  • 场景一：音乐播放器的随机播放
  • 场景二：游戏中的随机抽卡
  • 场景三：测试数据的随机生成
  • 场景四：图片轮播的随机顺序
  • 场景五：抽奖系统的随机抽取
• 总结

摘要

这道题其实挺有意思的，它要求我们设计一个能够打乱数组的类，并且能够随时恢复到原始状态。听起来简单，但实际做起来还是需要一些技巧的。关键点在于如何保证打乱后的数组所有排列都是等可能的，这就要用到经典的 Fisher-Yates 洗牌算法了。

这道题的核心在于如何高效地实现随机打乱，既要保证随机性，又要能快速恢复到原始状态。今天我们就用 Swift 来搞定这道题，顺便聊聊这种设计模式在实际开发中的应用场景，比如音乐播放器的随机播放、游戏中的随机抽卡、测试数据的随机生成等等。

描述

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

实现 Solution 类：

1. Solution(int[] nums)：使用整数数组 nums 初始化对象
2. int[] reset()：重设数组到它的初始状态并返回
3. 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 中的所有元素都是唯一的
• 最多可以调用 10^4 次 reset 和 shuffle

这道题的核心思路是什么呢？我们需要保存原始数组，这样 reset() 才能恢复到初始状态。对于 shuffle() 方法，我们需要使用 Fisher-Yates 洗牌算法来保证所有排列都是等可能的。这个算法的思想是从后往前遍历数组，对于每个位置，随机选择一个前面的位置（包括当前位置）进行交换。

题解答案

下面是完整的 Swift 解决方案：

classSolution{// 保存原始数组privatelet original:[Int]// 当前数组状态privatevar current:[Int]init(_ nums:[Int]){self.original = nums self.current = nums }/// 重设数组到它的初始状态并返回funcreset()->[Int]{ current = original return current }/// 返回数组随机打乱后的结果funcshuffle()->[Int]{// 从原始数组开始打乱 current = original // Fisher-Yates 洗牌算法for i instride(from: current.count -1, through:1, by:-1){// 随机选择一个索引 j，满足 0 <= j <= ilet j =Int.random(in:0...i)// 交换 current[i] 和 current[j] current.swapAt(i, j)}return current }}

题解代码分析

让我们一步步分析这个解决方案：

1. 数据结构的设计

这道题的关键在于如何保存原始数组和当前数组状态：

privatelet original:[Int]privatevar current:[Int]

我们使用了两个数组：

• original：一个常量数组，用来保存原始数组。使用 let 声明，确保它不会被修改，这样 reset() 才能正确恢复到初始状态
• current：一个可变数组，用来保存当前数组状态。每次 shuffle() 都会修改这个数组

2. 为什么需要两个数组？

如果只用一个数组，我们无法在 reset() 时恢复到原始状态，因为 shuffle() 会修改数组。所以我们需要：

• 保存原始数组的副本（original），用于 reset() 时恢复
• 使用当前数组（current）进行打乱操作

3. init() 方法详解

init(_ nums:[Int]){self.original = nums self.current = nums }

初始化方法的逻辑很简单：

1. 保存原始数组：将传入的数组保存到 original 中。注意这里 Swift 会自动创建数组的副本，因为数组是值类型
2. 初始化当前数组：将 current 也初始化为相同的数组

这里有个细节需要注意：Swift 中的数组是值类型，所以 self.original = nums 会创建 nums 的副本，而不是引用。这样即使外部修改了 nums，original 也不会受到影响。

4. reset() 方法详解

funcreset()->[Int]{ current = original return current }

reset() 方法的逻辑很简单：

1. 恢复原始数组：将 current 重新赋值为 original。由于数组是值类型，这里会创建一个新的副本
2. 返回当前数组：返回恢复后的数组

时间复杂度是 O(n)，因为需要复制数组。空间复杂度也是 O(n)，因为创建了数组的副本。

5. shuffle() 方法详解

这是最核心的方法，使用了 Fisher-Yates 洗牌算法：

funcshuffle()->[Int]{// 从原始数组开始打乱 current = original // Fisher-Yates 洗牌算法for i instride(from: current.count -1, through:1, by:-1){// 随机选择一个索引 j，满足 0 <= j <= ilet j =Int.random(in:0...i)// 交换 current[i] 和 current[j] current.swapAt(i, j)}return current }

shuffle() 方法的逻辑是：

1. 从原始数组开始：每次打乱都从原始数组开始，确保每次打乱都是独立的
2. Fisher-Yates 洗牌算法：从后往前遍历数组，对于每个位置 i：
   • 随机选择一个索引 j，满足 0 <= j <= i
   • 交换 current[i] 和 current[j]

6. Fisher-Yates 洗牌算法详解

Fisher-Yates 洗牌算法是生成随机排列的标准算法，它能够保证所有排列都是等可能的。

算法步骤：

假设数组有 n 个元素，索引从 0 到 n-1：

1. 从最后一个元素开始（索引 n-1）
2. 随机选择一个索引 j，满足 0 <= j <= n-1，然后交换 array[n-1] 和 array[j]
3. 继续处理倒数第二个元素（索引 n-2），随机选择一个索引 j，满足 0 <= j <= n-2，然后交换 array[n-2] 和 array[j]
4. 以此类推，直到处理到第二个元素（索引 1）

为什么这样能保证等概率？

对于每个位置 i，我们随机选择一个位置 j（0 <= j <= i）进行交换。这样：

• 最后一个元素（索引 n-1）有 n 种可能的位置（0 到 n-1）
• 倒数第二个元素（索引 n-2）有 n-1 种可能的位置（0 到 n-2，因为最后一个位置已经被占用）
• 以此类推

总的排列数是 n!，每个排列的概率都是 1/n!，所以是等概率的。

示例演示：

假设数组是 [1, 2, 3]，让我们看看 Fisher-Yates 算法是如何工作的：

初始状态：[1, 2, 3]

• i = 2：随机选择 j（0 <= j <= 2），假设 j = 0，交换后：[3, 2, 1]
• i = 1：随机选择 j（0 <= j <= 1），假设 j = 1，交换后：[3, 2, 1]（没有变化）
• i = 0：不需要处理（只有一个元素）

最终结果：[3, 2, 1]

如果再次执行：

• i = 2：随机选择 j（0 <= j <= 2），假设 j = 1，交换后：[1, 3, 2]
• i = 1：随机选择 j（0 <= j <= 1），假设 j = 0，交换后：[3, 1, 2]
• i = 0：不需要处理

最终结果：[3, 1, 2]

每次执行都会得到不同的随机排列。

7. Swift 中的 stride 函数

代码中使用了 stride(from:through:by:) 函数来从后往前遍历：

for i instride(from: current.count -1, through:1, by:-1){// ...}

这个函数的作用是：

• from: current.count - 1：从最后一个索引开始
• through: 1：到索引 1 结束（包括 1）
• by: -1：每次减 1

例如，如果数组有 5 个元素（索引 0-4），这个循环会依次处理索引 4, 3, 2, 1。

8. swapAt() 方法

Swift 数组提供了 swapAt(_:_:) 方法来交换两个位置的元素：

current.swapAt(i, j)

这等价于：

let temp = current[i] current[i]= current[j] current[j]= temp 

但 swapAt() 更简洁，而且性能更好（内部可能使用了优化）。

9. 边界情况处理

代码中处理了几个重要的边界情况：

1. 空数组：如果数组为空，current.count - 1 会是 -1，但 stride(from:through:by:) 不会执行循环，所以会直接返回空数组，这是正确的
2. 单元素数组：如果数组只有一个元素，stride(from:through:by:) 也不会执行循环（因为 through: 1 而 from: 0），会直接返回原数组，这也是正确的
3. 多次调用 shuffle()：每次调用都从原始数组开始，确保每次打乱都是独立的

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：基本操作

let solution =Solution([1,2,3])print("初始数组: \(solution.reset())")// [1, 2, 3]print("第一次打乱: \(solution.shuffle())")// 可能是 [3, 1, 2]print("第二次打乱: \(solution.shuffle())")// 可能是 [2, 3, 1]print("第三次打乱: \(solution.shuffle())")// 可能是 [1, 3, 2]print("重置: \(solution.reset())")// [1, 2, 3]

执行过程分析：

1. 初始化：original = [1, 2, 3], current = [1, 2, 3]
2. reset()：返回 [1, 2, 3]
3. shuffle()：
   • 从 [1, 2, 3] 开始
   • i = 2：随机选择 j，假设 j = 0，交换后：[3, 2, 1]
   • i = 1：随机选择 j，假设 j = 1，交换后：[3, 2, 1]
   • 返回 [3, 2, 1]
4. shuffle()：再次从 [1, 2, 3] 开始，得到不同的随机排列
5. reset()：恢复到 [1, 2, 3]

示例 2：题目示例

let solution =Solution([1,2,3])print("shuffle(): \(solution.shuffle())")// 例如：[3, 1, 2]print("reset(): \(solution.reset())")// [1, 2, 3]print("shuffle(): \(solution.shuffle())")// 例如：[1, 3, 2]

执行过程分析：

1. shuffle()：从 [1, 2, 3] 开始打乱，可能得到 [3, 1, 2]
2. reset()：恢复到 [1, 2, 3]
3. shuffle()：再次从 [1, 2, 3] 开始打乱，可能得到 [1, 3, 2]

示例 3：单元素数组

let solution =Solution([42])print("shuffle(): \(solution.shuffle())")// [42]print("reset(): \(solution.reset())")// [42]

执行过程分析：

对于单元素数组，stride(from: 0, through: 1, by: -1) 不会执行循环（因为 0 < 1），所以直接返回原数组，这是正确的。

示例 4：验证随机性

let solution =Solution([1,2,3,4])// 统计每种排列出现的次数var count:[String:Int]=[:]for_in0..<10000{let shuffled = solution.shuffle()let key = shuffled.map {String($0)}.joined(separator:",") count[key,default:0]+=1}print("10000 次打乱的结果分布（前10个）:")let sorted = count.sorted {$0.value >$1.value }.prefix(10)for(key, value)in sorted {print(" [\(key)]: \(value) 次")}

这个测试可以验证 Fisher-Yates 算法确实能产生等概率的随机排列。对于 4 个元素的数组，总共有 4! = 24 种排列，每种排列的期望出现次数是 10000 / 24 ≈ 416 次。

示例 5：多次 reset 和 shuffle

let solution =Solution([1,2,3,4,5])print("初始: \(solution.reset())")for i in1...5{print("第 \(i) 次打乱: \(solution.shuffle())")}print("重置后: \(solution.reset())")

这个测试展示了多次调用 shuffle() 和 reset() 的正确性。

时间复杂度

让我们分析一下每个操作的时间复杂度：

总体时间复杂度：

• init()：O(n)
• reset()：O(n)
• shuffle()：O(n)

对于题目约束（nums.length <= 50，最多调用 10^4 次 reset 和 shuffle），这个时间复杂度是完全可接受的。

优化思考：

虽然每次 shuffle() 都需要复制数组，但这是必要的，因为我们需要从原始数组开始打乱。如果我们在原数组上直接打乱，就无法保证每次打乱都是独立的。

空间复杂度

空间复杂度分析：

• original：存储原始数组，O(n)
• current：存储当前数组状态，O(n)

总空间复杂度：O(n)

其中 n 是数组的长度。我们使用了两个数组来保存数据，这是必要的，因为我们需要：

1. 保存原始数组，用于 reset() 时恢复
2. 保存当前数组状态，用于 shuffle() 时打乱

虽然使用了两个数组，但空间复杂度仍然是 O(n)，因为两个数组的大小都是 n。

实际应用场景

这种设计模式在实际开发中应用非常广泛：

场景一：音乐播放器的随机播放

在音乐播放器中，我们需要能够随机播放歌曲列表，并且能够随时恢复到原始顺序：

classMusicPlayer{privatelet playlist:[String]privatevar shuffledPlaylist:[String]privatevar currentIndex:Int=0init(songs:[String]){self.playlist = songs self.shuffledPlaylist = songs }funcshuffle(){// 使用 Fisher-Yates 算法打乱播放列表 shuffledPlaylist = playlist for i instride(from: shuffledPlaylist.count -1, through:1, by:-1){let j =Int.random(in:0...i) shuffledPlaylist.swapAt(i, j)} currentIndex =0}funcreset(){ shuffledPlaylist = playlist currentIndex =0}funcnext()->String?{guard currentIndex < shuffledPlaylist.count else{returnnil}let song = shuffledPlaylist[currentIndex] currentIndex +=1return song }}// 使用示例let player =MusicPlayer(songs:["Song1","Song2","Song3","Song4"]) player.shuffle()print("随机播放: \(player.next()??"无")")print("随机播放: \(player.next()??"无")") player.reset()print("顺序播放: \(player.next()??"无")")

这种场景下，我们需要能够随机播放歌曲，同时保留原始顺序，方便用户切换到顺序播放模式。

场景二：游戏中的随机抽卡

在卡牌游戏中，我们需要从卡池中随机抽取卡片，并且能够重置卡池：

classCardPool{privatelet originalCards:[Card]privatevar availableCards:[Card]init(cards:[Card]){self.originalCards = cards self.availableCards = cards }funcshuffle(){// 打乱可用卡片 availableCards = originalCards for i instride(from: availableCards.count -1, through:1, by:-1){let j =Int.random(in:0...i) availableCards.swapAt(i, j)}}funcreset(){ availableCards = originalCards }funcdrawCard()->Card?{guard!availableCards.isEmpty else{returnnil}return availableCards.removeFirst()}}

这种场景下，我们需要能够随机抽取卡片，并且能够重置卡池，让玩家重新开始。

场景三：测试数据的随机生成

在测试中，我们需要生成随机的测试数据，并且能够重置到初始状态：

classTestDataGenerator{privatelet originalData:[Int]privatevar shuffledData:[Int]init(data:[Int]){self.originalData = data self.shuffledData = data }funcshuffle(){ shuffledData = originalData for i instride(from: shuffledData.count -1, through:1, by:-1){let j =Int.random(in:0...i) shuffledData.swapAt(i, j)}}funcreset(){ shuffledData = originalData }funcgetRandomData()->[Int]{return shuffledData }}// 使用示例let generator =TestDataGenerator(data:Array(1...100)) generator.shuffle()let testData1 = generator.getRandomData() generator.shuffle()let testData2 = generator.getRandomData() generator.reset()let originalData = generator.getRandomData()

这种场景下，我们需要能够生成随机的测试数据，同时保留原始数据，方便重复测试。

场景四：图片轮播的随机顺序

在图片轮播中，我们需要能够随机显示图片，并且能够恢复到原始顺序：

classImageCarousel{privatelet originalImages:[UIImage]privatevar shuffledImages:[UIImage]privatevar currentIndex:Int=0init(images:[UIImage]){self.originalImages = images self.shuffledImages = images }funcshuffle(){ shuffledImages = originalImages for i instride(from: shuffledImages.count -1, through:1, by:-1){let j =Int.random(in:0...i) shuffledImages.swapAt(i, j)} currentIndex =0}funcreset(){ shuffledImages = originalImages currentIndex =0}funcnextImage()->UIImage?{guard currentIndex < shuffledImages.count else{returnnil}let image = shuffledImages[currentIndex] currentIndex +=1return image }}

这种场景下，我们需要能够随机显示图片，同时保留原始顺序，方便用户切换到顺序模式。

场景五：抽奖系统的随机抽取

在抽奖系统中，我们需要从参与者列表中随机抽取获奖者，并且能够重置：

classLotterySystem{privatelet originalParticipants:[String]privatevar shuffledParticipants:[String]init(participants:[String]){self.originalParticipants = participants self.shuffledParticipants = participants }funcshuffle(){ shuffledParticipants = originalParticipants for i instride(from: shuffledParticipants.count -1, through:1, by:-1){let j =Int.random(in:0...i) shuffledParticipants.swapAt(i, j)}}funcreset(){ shuffledParticipants = originalParticipants }funcdrawWinner()->String?{guard!shuffledParticipants.isEmpty else{returnnil}return shuffledParticipants.removeFirst()}}

这种场景下，我们需要能够随机抽取获奖者，同时保留原始参与者列表，方便重新开始抽奖。

总结

这道题虽然看起来简单，但实际上涉及了很多重要的算法和设计思想：

1. Fisher-Yates 洗牌算法：这是生成随机排列的标准算法，能够保证所有排列都是等可能的。算法的核心思想是从后往前遍历数组，对于每个位置，随机选择一个前面的位置进行交换。
2. 状态管理：我们需要保存原始数组和当前数组状态，这样才能在 reset() 时恢复到初始状态。这在实际开发中是一个常见的设计模式。
3. 时间复杂度优化：虽然每次 shuffle() 都需要 O(n) 的时间，但这是必要的，因为我们需要从原始数组开始打乱，保证每次打乱都是独立的。
4. 实际应用：这种设计模式在实际开发中应用广泛，如音乐播放器的随机播放、游戏中的随机抽卡、测试数据的随机生成、图片轮播的随机顺序、抽奖系统的随机抽取等。

关键点总结：

• 使用 Fisher-Yates 洗牌算法保证等概率随机排列
• 保存原始数组用于 reset() 时恢复
• 每次 shuffle() 都从原始数组开始，保证独立性
• 所有操作的时间复杂度都是 O(n)
• 空间复杂度是 O(n)

算法优势：

1. 正确性：Fisher-Yates 算法能够保证所有排列都是等概率的
2. 效率：时间复杂度是 O(n)，对于题目约束完全可接受
3. 简单：实现简单，容易理解和维护

注意事项：

1. 数组复制：Swift 中的数组是值类型，所以 current = original 会创建副本，这是正确的
2. 随机性：使用 Int.random(in: 0...i) 来生成随机数，确保随机性
3. 边界情况：需要处理空数组和单元素数组的情况