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

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$。

代码如下所示：

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

上述代码比较晦涩难懂，优化为下面的代码：

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$ 个元素。

方法二：Knuth洗牌算法

思路与算法：

易知排列总数是：

$n! = n \times (n-1)!$

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

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

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

可以理解为把 $n!$ 分成 $n$ 段，先选择其中一段，里面有 $(n-1)!$ 个元素，我们把这 $(n-1)!$ 个情况再分成 $n-1$ 段，从中随机选一个，这样每个数都有相等的概率被放到任意一个位置中，即每个位置中出现任意一个数的概率都是相同的。

代码如下所示：

// 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)$ 来初始化 $\textit{original}$
  • $\texttt{reset}$：$O(1)$。
  • $\textit{shuffle}$：$O(n)$。

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

---

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. 😉😃💗