【Leetcode算法题】384. 打乱数组

By Long Luo

今天Leetcode的每日一题是:384. 打乱数组,题目如下:

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
384. 打乱数组

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

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

示例:

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如,返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如,返回 [1, 3, 2]

提示:
1 <= nums.length <= 200
-10^6 <= nums[i] <= 10^6
nums 中的所有元素都是 唯一的
最多可以调用5 * 10^4次reset和shuffle

方法一:暴力 + 随机数

思路与算法:

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

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

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

但这道题目测试用例缺陷,这种计算居然AC了,因为原始数组元素可能是0。

代码如下所示:

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;
}
}

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为数组中的元素数量。。

初始化: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个元素。

方法二:

思路与算法: