Cracking the coding interview--Q20.3

Hawstein | February 25, 2013

题目

原文:

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

译文:

写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。

解答

这道题目和随机洗牌问题类似,只需要随机选取1个元素, 然后在剩下的元素里面随机选取下一个元素,不断这样操作即可。

这样做能保证每个元素选中的概率一样吗?也就是选中每个元素的概率都是1/n? 答案是YES,让我们来做一下简单的计算。

  • 选第1个元素:在n个中随机选,因此概率为1/n

  • 选第2个元素:在剩下的n-1个中随机选:1/(n-1),由于第1次没有选中它, 而是在另外n-1个中选:(n-1)/n,因此概率为:(n-1)/n * 1/(n-1) = 1/n

  • 选第3个元素:同上:(n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n

。。。

因此,按照这种方法选取k个元素,每个元素都是以1/n的概率被选出来的。代码如下: 选出的m个数放到数组前m个位置。

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
#include <iostream>
#include <cstdlib>
using namespace std;

void Swap(int &a, int &b){// 有可能swap同一变量,不能用异或版本
    int t = a;
    a = b;
    b = t;
}
void PickMRandomly(int a[], int n, int m){
    for(int i=0; i<m; ++i){
        int j = rand() % (n-i) + i;// 产生i到n-1间的随机数
        Swap(a[i], a[j]);
    }
}
int main(){
    srand((unsigned)time(0));
    int n = 9, m = 5;
    int a[] = {
        1, 2, 3, 4, 5, 6, 7, 8, 9
    };
    PickMRandomly(a, n, m);
    for(int i=0; i<m; ++i)
        cout<<a[i]<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview

声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2013/02/25/20.3/