By Long Luo
Leetcode 384. 打乱数组 题解。
对于一个数组，所有的排列一共存在多少种呢？根据排列组合，对 \(n\) 个不同元素进行排列，从第 \(1\) 位开始枚举，选择 \(1~n\) 中的某一个，然后进行第 \(2\) 位的枚举，选择剩下的 \(n-1\) 个中的某一个，依次直到选取最后一个元素，很容易知道这样的排列总数为 \(n!\)。
洗牌算法的核心在于能等概率的产生所有可能的排列情况。
方法一：暴力 + 随机数
思路与算法：
看到这个题目，首先就想到的是新建一个数组 \(\textit{src}\)，用于存储原始数组，然后调用reset()时直接返回这个数组 \(\textit{src}\)。
然后，如何随机打乱一个数组呢？
新建一个数组，因为数组元素初始值都是 \(0\)，用一个变量 \(\textit{idx}\) 标记新数组索引，获取一个 \([0, \textit{len}]\) 的随机数 \(\textit{seed}\)，当判断新数组元素为 \(0\) 时，新数组 \(\textit{res[seed]}\) 等于 \(\textit{src[idx]}\)，然后 \(\textit{idx}\) 加 \(1\)。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
int len;
int[] src;
public Solution(int[] nums) {
len = nums.length;
src = new int[len];
System.arraycopy(nums, 0, src, 0, len);
}
public int[] reset() {
return src;
}
public int[] shuffle() {
int[] res = new int[len];
int seed = len - 1;
Random random = new Random();
int idx = 0;
while (idx < len) {
seed = random.nextInt(len);
while (res[seed] == 0) {
res[seed] = src[idx];
idx++;
}
}
return res;
}
}
|
上述代码比较晦涩难懂，优化为下面的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
int len;
int[] original;
Random random = new Random();
public Solution(int[] nums) {
this.len = nums.length;
original = new int[len];
System.arraycopy(nums, 0, original, 0, len);
}
public int[] reset() {
return original;
}
public int[] shuffle() {
int[] shuffled = new int[len];
List<Integer> numsList = new ArrayList<>();
for (int x : original) {
numsList.add(x);
}
for (int i = 0; i < len; i++) {
int idx = random.nextInt(numsList.size());
shuffled[i] = numsList.get(idx);
numsList.remove(idx);
}
return shuffled;
}
}
|
复杂度分析：
- 时间复杂度：
- 初始化：\(O(n)\)，需要 \(O(n)\) 来初始化 \(\textit{original}\)
- \(\texttt{reset}\)：\(O(1)\)。
- \(\texttt{shuffle}\)：\(O(n^2)\)。需要遍历 \(n\) 个元素，每个元素需要 \(O(n-k)\) 的时间从 \(\textit{nums}\) 中移除第 \(k\) 个元素。
- 空间复杂度： \(O(n)\) ，记录初始状态和临时的乱序数组均需要存储 \(n\) 个元素。