打乱数组

难度: Medium

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

Submission

运行时间: 62 ms

内存: 19.6 MB

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums[:]
    def reset(self) -> List[int]:
        return self.original

    def shuffle(self) -> List[int]:
        n = len(self.nums)
        for i in range(n):
            idx = random.randrange(i, n)
            self.nums[i], self.nums[idx] = self.nums[idx], self.nums[i]
        return self.nums



# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

Explain

这个题解的主要思路是实现一个打乱数组的算法，同时允许随时将数组重置为原始状态。初始化时，存储原始数组的一个副本。重置功能只需返回这个原始副本。打乱功能则通过Fisher-Yates洗牌算法来实现，这个算法通过遍历数组，并在当前位置与后续位置（包括当前位置自身）中随机选择一个进行交换，从而确保每个元素随机出现在任何位置。

时间复杂度: O(n)

空间复杂度: O(n)


    class Solution:

        def __init__(self, nums: List[int]):
            self.nums = nums  # 存储传入的数组
            self.original = nums[:]  # 存储原始数组的副本以便reset时使用

        def reset(self) -> List[int]:
            return self.original  # 返回原始数组的副本，实现数组的重置

        def shuffle(self) -> List[int]:
            n = len(self.nums)  # 获取数组长度
            for i in range(n):
                idx = random.randrange(i, n)  # 生成一个从i到n-1的随机索引
                self.nums[i], self.nums[idx] = self.nums[idx], self.nums[i]  # 交换当前元素与随机选中的元素
            return self.nums  # 返回打乱后的数组

Explore

Fisher-Yates洗牌算法通过每次从未处理的部分随机选取一个元素与当前位置的元素进行交换来实现打乱。这种方法从第一个元素开始，直到最后一个元素。每次交换时，每个元素都有相等的机会被选中。这样确保了每个位置的元素都是随机从剩余的未被选中的元素中选出的，从而保证了每个元素出现在任何位置的概率是均等的。

是的，在`shuffle()`方法中使用`random.randrange(i, n)`确实考虑了所有元素的均匀随机性。这个函数每次调用时，会从当前索引`i`到数组末尾的索引`n-1`中随机选择一个索引。因为每次都是从当前元素到数组末尾的元素中随机选择，所以每个元素都有均等的机会在每次迭代中被选中，从而保证了打乱过程中元素的均匀随机性。

在`shuffle()`方法中交换当前索引`i`和随机索引`idx`的值而不是直接移动元素，是为了确保打乱的过程中每个元素仅被移动一次，并且保持数组的完整性。如果我们只是简单地将随机索引的元素放到当前位置，那么可能会导致某些元素被重复使用而其他元素被遗漏，从而破坏均匀随机性。通过交换元素，我们确保了每个位置都有可能被任何元素占据，且每个元素都只被处理一次，从而有效地保持了打乱的随机性和公平性。