LeetCode 384 Shuffle an Array

LeetCode

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.

Example 1:

Input
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Constraints: 1 <= nums.length <= 200
-10<sup>6</sup> <= nums[i] <= 10<sup>6</sup> All the elements of nums are unique.
At most `5 10<sup>4</sup>calls **in total** will be made toresetandshuffle`.

题目大意：

随机重排数组

解题思路：

水塘抽样法

先看算法，再理解，第i个元素会被交换的概率：
某一个元素保留概率为(n - i) / (n - i + 1)
某一个元素交换概率为1 / (n - i)
所以从左到右遍历到第i个元素时，它被交换到后面的概率为 所有前面都保留 乘以 第i轮循环时被交换：

(n - 1) / n * (n - 2) / (n - 1) ... (n - i) / (n - i + 1) * 1 / (n - i)

前面都约了，最后等于1 / n

解题步骤：

N/A

注意事项：

1. 死记算法，跟后面的元素互换
2. 复制原数组以防被改

Python代码：

def __init__(self, nums: List[int]):
	self.original = list(nums)
	self.nums = nums

def reset(self) -> List[int]:
	return list(self.original)

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

算法分析：

时间复杂度为O(n)，空间复杂度O(1)