洗牌算法

发布： 分类： 评论： 阅读：

之前两次面试都被问到洗牌算法，虽然不是直接问的，但都是基于洗牌算法的。结果第一次被问到之后没有重视，导致在一个地方栽了两次坑。。。😭

洗牌算法，就是给你一个1到n的序列，让你随机打乱，保证每个数出现在任意一个位置的概率相同。换句话说，经过洗牌的数组的排列组合有n!种可能。

解法

Fisher-Yates Shuffle 算法 动态演示

  • 思想：从原始数组中随机取一个之前没有取过的数字到新的数组中。

  • 步骤：

    1
    2
    3
    4
    5
    1. 初始化原始数组和新数组，原始数组长度为n（已知）；
    2. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（数组下标从0开始）；
    3. 从剩下的k个数中第p个数取出；
    4. 重复步骤2，3直到数字全部取完；
    5. 从步骤3中去除的数字序列便是一个打乱的数列。

  • 证明：证明其随机性，即每个元素被放置在新数组中的第 i 个位置是 1/n
    一个元素m被放入第 i 个位置的概率 P = 前 i-1 个位置选择元素时没有选中m的概率 * 第 i 个位置选中m的概率，即:

    $$P = \frac{n-1}{n} * \frac{n-2}{n-1} * … * \frac{n-i+1}{n-i+2} * \frac{1}{n-i+1} = \frac{1}{n}$$

  • 时间复杂度为O(n*n),空间复杂度为O(n).

  • 时间复杂度为O(n*n) 是因为我们要删除list中的元素，那么也就是要将后面的元素都向前移动一位，导致时间复杂度为O(n*n) .

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Random;

public ArrayList Fisher_Yates_Shuffle(ArrayList<Integer> arr) {
    ArrayList<Integer> tar_arr = new ArrayList();
    int n = arr.size();
    for(int i=0;i<n;i++) {
        // 生成0-n的随机数，包括0不包括n -- [0,n)
        int p =(int)(Math.random()*(n-i));
        tar_arr.add(arr.get(p));
        arr.remove(p);  // 删除index=p位置的元素
    }
    return tar_arr;
}

Knuth-Durstenfeld Shuffle 算法

  • 对1的算法进行了改进，直接在原始数组上进行交换，而不必开辟额外的数组，节省空间。
  • 思想：每次从未处理的数字中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。
  • 步骤：
    1
    2
    3
    4
    5
    6
    7
    1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
    2. 生成一个从 0 到 n - 1 的随机数 x；
    3. 输出 arr 下标为 x 的数值，即为第一个随机数；
    4. 将 arr 的尾元素和下标为 x 的元素互换；
    5. 同2，生成一个从 0 到 n - 2 的随机数 x；
    6. 输出 arr 下标为 x 的数值，为第二个随机数；
    7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
  • 时间复杂度为O(n),空间复杂度为O(1)。缺点：必须知道数组长度n.
1
2
3
4
5
6
7
8
9
10
import java.util.Random;

public void Knuth_Durstenfeld_Shuffle(int[] arr) {
    int n = arr.length;
    for(int i=0;i<n;i++) {
        // 生成0-n的随机数，包括0不包括n -- [0,n)
        int p =(int)(Math.random()*(n-i));
        swap(arr, p, n-i-1);
    }
}

Inside-Out Algorithm 算法

  • Knuth-Durstenfeld Shuffle 是一个内部打乱的算法，算法完成后原始数据被直接打乱，尽管这个方法可以节省空间，但在有些应用中可能需要保留原始数据，所以需要另外开辟一个数组来存储生成的新序列。
  • Inside-Out Algorithm 算法是既可以开辟新的空间，而且不需要对原数组进行删除操作。
  • 思想：设一游标i从前向后扫描原始数据的拷贝，在[0, i]之间随机一个下标p，然后用位置p的元素替换掉位置i的数字，再用原始数据位置i的元素替换掉拷贝数据位置p的元素。其作用相当于在拷贝数据中交换i与p位置处的值。
  • 时间复杂度为O(n),空间复杂度为O(n)
  • 这个算法的一个优点就是可以处理n未知的数组。
  • 这个相当于：1*2*3*4*5*6*7*...*n = n! 种可能情况。
  • 而前两种洗牌算法都相当于：n*n-1*n-2*n-3*...*1 = n! 种可能情况。
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.Random;

public int[] Inside_Out_Shuffle(int[] arr) {
    int[] tar_arr = new int[arr.length];
    tar_arr = arr.clone();
    for(int i=0;i<arr.length;i++) {
        int p = (int)(Math.random()*(i+1));
        tar_arr[i] = tar_arr[p];
        tar_arr[p] = arr[i];
    }
    return tar_arr;
}

注：之前Inside-Out Algorithm看了半天，没搞明白为什么需要那么麻烦两个数组替换来替换去的。。搞这么一波骚操作，但其实，Inside-Out Algorithm算法和Knuth-Durstenfeld Shuffle 算法的区别就在于一个原地打乱，一个在新数组上打乱。那么我们就可以先拷贝一份原数组，然后在新数组上按照Knuth-Durstenfeld Shuffle 算法的方法执行一遍就行了。两个数组替换实际上就是代替了原来的swap操作，不用额外开辟一个空间给暂存数据。而且Inside-Out Algorithm是从前向后处理的，可以处理n未知的数组。

例题

leetcode 384. 数组随即洗牌

1