[Leetcode][384. 打乱数组] 2种方法:暴力 和 洗牌算法

By Long Luo

Leetcode 384. 打乱数组 题解。

对于一个数组,所有的排列一共存在多少种呢?根据排列组合,对nn个不同元素进行排列,从第11位开始枚举,选择1 n1~n中的某一个,然后进行第22位的枚举,选择剩下的n1n-1个中的某一个,依次直到选取最后一个元素,很容易知道这样的排列总数为n!n!

洗牌算法的核心在于能等概率的产生所有可能的排列情况。

方法一:暴力 + 随机数

思路与算法:

看到这个题目,首先就想到的是新建一个数组src\textit{src},用于存储原始数组,然后调用reset()时直接返回这个数组src\textit{src}

然后,如何随机打乱一个数组呢?

新建一个数组,因为数组元素初始值都是00,用一个变量idx\textit{idx}标记新数组索引,获取一个[0,len][0, \textit{len}]的随机数seed\textit{seed},当判断新数组元素为00时,新数组res[seed]\textit{res[seed]}等于src[idx]\textit{src[idx]},然后idx\textit{idx}11

代码如下所示:

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),需要O(n)O(n)来初始化original\textit{original}
    • reset\texttt{reset}O(1)O(1)
    • shuffle\texttt{shuffle}O(n2)O(n^2)。需要遍历nn个元素,每个元素需要O(nk)O(n-k)的时间从nums\textit{nums}中移除第kk个元素。
  • 空间复杂度:O(n),记录初始状态和临时的乱序数组均需要存储nn个元素。

方法二:Knuth洗牌算法

思路与算法:

易知排列总数是:

n!=n×(n1)!n! = n \times (n-1)!

这里的nn就是你先挑选出第一个元素的种类数,而(n1)!(n-1)!就是对其他元素的排列。

我们需要挑选一种洗牌方案:

  1. 先等概率的从nn个元素中挑选一个作为第一个元素;
  2. 再对剩下的n1n-1个元素做类似的选择;
  3. 依次类推,直到没有元素可选为此。

可以理解为把n!n!分成nn段,先选择其中一段,里面有(n1)!(n-1)!个元素,我们把这(n1)!(n-1)!个情况再分成n1n-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
// Knuth
class Solution_Knuth {
int len;
int[] original;
Random random = new Random();

public Solution_Knuth(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];
System.arraycopy(original, 0, shuffled, 0, len);
for (int i = len - 1; i >= 0; i--) {
int idx = random.nextInt(i + 1);
int temp = shuffled[i];
shuffled[i] = shuffled[idx];
shuffled[idx] = temp;
}

return shuffled;
}
}

复杂度分析:

  • 时间复杂度:

    • 初始化:O(n)O(n),需要O(n)O(n)来初始化original\textit{original}
    • reset\texttt{reset}O(1)O(1)
    • shuffle\textit{shuffle}O(n)O(n)
  • 空间复杂度:O(n)。记录初始状态和临时的乱序数组均需要存储nn个元素。


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗