By Long Luo
Leetcode 384. 打乱数组 题解。
对于一个数组,所有的排列一共存在多少种呢?根据排列组合,对 n n n 个不同元素进行排列,从第 1 1 1 位开始枚举,选择 1 n 1~n 1 n 中的某一个,然后进行第 2 2 2 位的枚举,选择剩下的 n − 1 n-1 n − 1 个中的某一个,依次直到选取最后一个元素,很容易知道这样的排列总数为 n ! n! n ! 。
洗牌算法的核心 在于能等概率的产生所有可能的排列 情况。
方法一:暴力 + 随机数
思路与算法:
看到这个题目,首先就想到的是新建一个数组 src \textit{src} src ,用于存储原始数组,然后调用reset()
时直接返回这个数组 src \textit{src} src 。
然后,如何随机打乱一个数组呢?
新建一个数组,因为数组元素初始值都是 0 0 0 ,用一个变量 idx \textit{idx} idx 标记新数组索引,获取一个 [ 0 , len ] [0, \textit{len}] [ 0 , len ] 的随机数 seed \textit{seed} seed ,当判断新数组元素为 0 0 0 时,新数组 res[seed] \textit{res[seed]} res[seed] 等于 src[idx] \textit{src[idx]} src[idx] ,然后 idx \textit{idx} idx 加 1 1 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; } }
复杂度分析:
方法二:Knuth洗牌算法
思路与算法:
易知排列总数是:
n ! = n × ( n − 1 ) ! n! = n \times (n-1)!
n ! = n × ( n − 1 ) !
这里的n n n 就是你先挑选出第一个元素的种类数,而 ( n − 1 ) ! (n-1)! ( n − 1 ) ! 就是对其他元素的排列。
我们需要挑选一种洗牌方案:
先等概率的从 n n n 个元素中挑选一个作为第一个元素;
再对剩下的 n − 1 n-1 n − 1 个元素做类似的选择;
依次类推,直到没有元素可选为此。
可以理解为把 n ! n! n ! 分成 n n n 段,先选择其中一段,里面有 ( n − 1 ) ! (n-1)! ( n − 1 ) ! 个元素,我们把这 ( n − 1 ) ! (n-1)! ( n − 1 ) ! 个情况再分成 n − 1 n-1 n − 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 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; } }
复杂度分析:
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 . 😉😃💗