题目

给你一个整数数组nums，设计算法来打乱一个没有重复元素的数组。

实现 Solution class ：

  • Solution（int[] nums) 使用整数数组 nums 初始化对象
  • int [] reset() 重设数组到它的初始状态并返回
  • int [] shuffle() 返回数组随机打乱后的结果

image.png

思路

方法一：暴力法

对于 reset() 来说，可以初始化的时候拷贝一份 nums ，在调用reset() 时候直接返回拷贝的结果。

对于 shuffle() 来说，每次从剩下的元素中随机取一个数。

如何使得返回概率相同？
每次随机拿一个数（不放回），所有的数都会被等概率选中。
证明：
image.png
由上可以证明，不管哪一轮摸到哪一个数字，概率都是 1/n 。

  1. class Solution:
  3.     def __init__(self, nums: List[int]):
  4.         self.nums = nums
  5.         self.original = nums[:]
  8.     def reset(self) -> List[int]:
  9.         """
  10.         Resets the array to its original configuration and return it.
  11.         """
  12.         return self.original
  15.     def shuffle(self) -> List[int]:
  16.         """
  17.         Returns a random shuffling of the array.
  18.         """
  19.         aux = self.nums[:]
  20.         for num in range(len(self.nums)):
  21.             remove_ind = random.randrange(0, len(self.nums)) # 随机返回range(0, len(self.nums))中的一个数
  22.             aux[num] = self.nums.pop(remove_ind)
  23.         self.nums = aux
  24.         return aux
  26. # Your Solution object will be instantiated and called as such:
  27. # obj = Solution(nums)
  28. # param_1 = obj.reset()
  29. # param_2 = obj.shuffle()

时间复杂度：O(n^2)。（list.pop(index)时间复杂度为O(n))
空间复杂度：O(n)

思路二：Fisher-Yates洗牌算法

如何优化呢？对于 shuffle() 操作，可以让数组中的元素相互交换，这样就避免了迭代修改数组的时间了。

如何模拟从数组中采样一个数不放回的操作？

  • 迭代整个数组nums， i
    • 在范围range(i, len(nums))中，随机生成一个下标j，交换nums[i]和nums[j]；
  1. class Solution:
  3.     def __init__(self, nums: List[int]):
  4.         self.nums = nums
  5.         self.original = nums[:]
  8.     def reset(self) -> List[int]:
  9.         """
  10.         Resets the array to its original configuration and return it.
  11.         """
  12.         return self.original
  15.     def shuffle(self) -> List[int]:
  16.         """
  17.         Returns a random shuffling of the array.
  18.         """
  19.         for i in range(len(self.nums)):
  20.             swap_ind = random.randrange(i, len(self.nums)) # 随机返回range(0, len(self.nums))中的一个数
  21.             self.nums[i], self.nums[swap_ind] = self.nums[swap_ind], self.nums[i]
  23.         return self.nums
  25. # Your Solution object will be instantiated and called as such:
  26. # obj = Solution(nums)
  27. # param_1 = obj.reset()
  28. # param_2 = obj.shuffle()

时间复杂度：O(n)
空间复杂度：O(n)