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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 384. 打乱数组 题解。

对于一个数组，所有的排列一共存在多少种呢？根据排列组合，对 nn 个不同元素进行排列，从第 11 位开始枚举，选择 1 n1~n 中的某一个，然后进行第 22 位的枚举，选择剩下的 n−1n-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(n−k)O(n-k) 的时间从 nums\textit{nums} 中移除第 kk 个元素。

  • 空间复杂度：O(n)，记录初始状态和临时的乱序数组均需要存储 nn 个元素。

方法二：Knuth洗牌算法

思路与算法：

易知排列总数是：

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

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

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

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

可以理解为把 n!n! 分成 nn 段，先选择其中一段，里面有 (n−1)!(n-1)! 个元素，我们把这 (n−1)!(n-1)! 个情况再分成 n−1n-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. 😉😃💗