文章目录

出处方法1 暴力方法2 洗牌算法

出处

非常常见的洗牌算法，还有一道leetcode的题目

384 . 打乱数组 https://leetcode-cn.com/problems/shuffle-an-array/

方法1 暴力

如果没想到洗牌算法的话，通常想到的做法就是每次从数组里面随机取出一个数字，然后把这个数组从数组中移除，重复n次，最后返回由取出的数组成的数组即可 这样做时间复杂度是O(N^2) leetcode的官方答案

class Solution { private int[] array; private int[] original; private Random rand = new Random(); private List<Integer> getArrayCopy() { List<Integer> asList = new ArrayList<Integer>(); for (int i = 0; i < array.length; i++) { asList.add(array[i]); } return asList; } public Solution(int[] nums) { array = nums; original = nums.clone(); } public int[] reset() { array = original; original = original.clone(); return array; } public int[] shuffle() { List<Integer> aux = getArrayCopy(); for (int i = 0; i < array.length; i++) { int removeIdx = rand.nextInt(aux.size()); array[i] = aux.get(removeIdx); aux.remove(removeIdx); } return array; } } 作者：LeetCode 链接：https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法2 洗牌算法

JAVA代码

class Solution { private int[] A; private int[] B; public Solution(int[] nums) { A=nums; B=Arrays.copyOf(nums,nums.length); } /** Resets the array to its original configuration and return it. */ public int[] reset() { return B; } /** Returns a random shuffling of the array. */ public int[] shuffle() { int n=A.length; for(int i=0;i<n;i++){ int r = i + (int)(Math.random() * ((n-i))); int t=A[i]; A[i]=A[r]; A[r]=t; } return A; } }

注意随机数的范围是[i,n-1]的，已经交换过的位置不需要再考虑