算法：给定 n 个不同元素的数组，设计算法等概率取 m 个不同的元素

有几种算法可以实现从n个不同元素的数组中等概率地取出m个不同元素，

其中一种是Knuth-Durstenfeld Shuffle算法，它的思想是：

• 将1到n的数字存到数组中
• 从数组中取一个1到剩下数字个数的随机数k
• 从低位开始，将数组第k个数字取出，并保存到结果数组末尾
• 重复第2步，直到取出m个数字

这种算法的时间复杂度是O (n)，空间复杂度是O (m)。

用Java语言实现的话，可以参考以下代码：

import java.util.Random;

public class RandomSelect {

    // 从n个不同元素的数组中等概率地取出m个不同元素
    public static int[] select(int[] array, int m) {
        int n = array.length;
        if (m > n) {
            throw new IllegalArgumentException("m cannot be larger than n");
        }
        int[] result = new int[m]; // 存放结果的数组
        Random random = new Random(); // 随机数生成器
        for (int i = 0; i < m; i++) {
            int k = random.nextInt(n - i) + i; // 生成一个i到n-1之间的随机数
            result[i] = array[k]; // 将第k个元素放入结果数组
            swap(array, i, k); // 将第k个元素与第i个元素交换，保证已选中的元素不会再被选中
        }
        return result;
    }

    // 交换数组中两个位置的元素
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 测试数组
        int m = 4; // 要取出的元素个数
        int[] result = select(array, m); // 调用算法
        for (int num : result) { // 打印结果
            System.out.print(num + " ");
        }
    }
}

这种算法有什么优缺点？

Knuth-Durstenfeld Shuffle算法的优点

• 是它的时间复杂度和空间复杂度都很低，只需要O (n)的时间和O (1)的空间，
• 而且能保证每个元素出现在每个位置上的概率相等。

它的缺点

• 是它是一个in-place算法，会改变原始数据的顺序，而有些场景中我们需要保留原始数据。
• 另外，它依赖于随机数生成器的质量，如果随机数生成器不够均匀或者有偏差，那么洗牌的结果也会受到影响。