0384. 打乱数组 #
- 标签:数组、数学、随机化
- 难度:中等
题目大意 #
描述:给定一个整数数组 nums
。
要求:设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是等可能的。
实现 Solution class
:
Solution(int[] nums)
使用整数数组nums
初始化对象。int[] reset()
重设数组到它的初始状态并返回。int[] shuffle()
返回数组随机打乱后的结果。
说明:
- $1 \le nums.length \le 50$。
- $-10^6 \le nums[i] \le 10^6$。
nums
中的所有元素都是 唯一的。- 最多可以调用 104 次
reset
和shuffle
。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:洗牌算法 #
题目要求在打乱顺序后,数组的所有排列应该是等可能的。对于长度为 n
的数组,我们可以把问题转换为:分别在 n
个位置上,选择填入某个数的概率是相同。具体选择方法如下:
- 对于第
0
个位置,我们从0 ~ n - 1
总共n
个数中随机选择一个数,将该数与第0
个位置上的数进行交换。则每个数被选到的概率为 $\frac{1}{n}$。 - 对于第
1
个位置,我们从剩下n - 1
个数中随机选择一个数,将该数与第1
个位置上的数进行交换。则每个数被选到的概率为 $\frac{n - 1}{n} \times \frac{1}{n - 1} = \frac{1}{n}$ (第一次没选到并且第二次被选中)。 - 对于第
2
个位置,我们从剩下n - 2
个数中随机选择一个数,将该数与第2
个位置上的数进行交换。则每个数被选到的概率为 $\frac{n - 1}{n} \times \frac{n - 2}{n - 1} \times \frac{1}{n - 2} = \frac{1}{n}$ (第一次没选到、第二次没选到,并且第三次被选中)。 - 依次类推,对于每个位置上,每个数被选中的概率都是 $\frac{1}{n}$。
思路 1:洗牌算法代码 #
|
|