LeetCode 384 打乱数组 Swift 实现与 Fisher-Yates 算法解析

提示：

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

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

题解答案

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

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

题解代码分析

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

1. 数据结构的设计

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

private let original: [Int]
private var 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() 方法详解

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

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

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

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

5. shuffle() 方法详解

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

func shuffle() -> [Int] {
    // 从原始数组开始打乱
    current = original
    // Fisher-Yates 洗牌算法
    for i in stride(from: current.count - 1, through: 1, by: -1) {
        // 随机选择一个索引 j，满足 0 <= j <= i
        let 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 in stride(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 _ in 0..<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 in 1...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。

实际应用场景

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

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

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

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

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

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

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

class CardPool {
    private let originalCards: [Card]
    private var availableCards: [Card]
    
    init(cards: [Card]) {
        self.originalCards = cards
        self.availableCards = cards
    }
    
    func shuffle() {
        // 打乱可用卡片
        availableCards = originalCards
        for i in stride(from: availableCards.count - 1, through: 1, by: -1) {
            let j = Int.random(in: 0...i)
            availableCards.swapAt(i, j)
        }
    }
    
    func reset() {
        availableCards = originalCards
    }
    
    func drawCard() -> Card? {
        guard !availableCards.isEmpty else { return nil }
        return availableCards.removeFirst()
    }
}

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

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

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

class TestDataGenerator {
    private let originalData: [Int]
    private var shuffledData: [Int]
    
    init(data: [Int]) {
        self.originalData = data
        self.shuffledData = data
    }
    
    func shuffle() {
        shuffledData = originalData
        for i in stride(from: shuffledData.count - 1, through: 1, by: -1) {
            let j = Int.random(in: 0...i)
            shuffledData.swapAt(i, j)
        }
    }
    
    func reset() {
        shuffledData = originalData
    }
    
    func getRandomData() -> [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()

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

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

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

class ImageCarousel {
    private let originalImages: [UIImage]
    private var shuffledImages: [UIImage]
    private var currentIndex: Int = 0
    
    init(images: [UIImage]) {
        self.originalImages = images
        self.shuffledImages = images
    }
    
    func shuffle() {
        shuffledImages = originalImages
        for i in stride(from: shuffledImages.count - 1, through: 1, by: -1) {
            let j = Int.random(in: 0...i)
            shuffledImages.swapAt(i, j)
        }
        currentIndex = 0
    }
    
    func reset() {
        shuffledImages = originalImages
        currentIndex = 0
    }
    
    func nextImage() -> UIImage? {
        guard currentIndex < shuffledImages.count else { return nil }
        let image = shuffledImages[currentIndex]
        currentIndex += 1
        return image
    }
}

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

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

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

class LotterySystem {
    private let originalParticipants: [String]
    private var shuffledParticipants: [String]
    
    init(participants: [String]) {
        self.originalParticipants = participants
        self.shuffledParticipants = participants
    }
    
    func shuffle() {
        shuffledParticipants = originalParticipants
        for i in stride(from: shuffledParticipants.count - 1, through: 1, by: -1) {
            let j = Int.random(in: 0...i)
            shuffledParticipants.swapAt(i, j)
        }
    }
    
    func reset() {
        shuffledParticipants = originalParticipants
    }
    
    func drawWinner() -> String? {
        guard !shuffledParticipants.isEmpty else { return nil }
        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. 边界情况：需要处理空数组和单元素数组的情况