问题描述

从一个预先不知道其大小的集合中随机选出K个数字。

算法

Input: K，和一系列数字。

Output: 随机选出的K个数字。

R := [ ];     # 初始化为一个空数组。
N := 0;       # 已经考虑的数字的个数。
for next number i
begin
    N := N + 1;
    if size(R) < K
    then
        R := [ R, i ];      # 将数字i添加到数组R中。
    else
        j := randint(0, N);
        if j < K
        then
            R[j] = i;
        end
    end
end

其中randint(0, N)等概率地返回[0, N)中的一个整数。结束后R中的K个数字就是我们需要的。