《Cracking the Coding Interview》——第18章：难题—

《Cracking the Coding Interview》——第18章：难题——题目3

2014-04-29 01:02

题目：从m个整数里随机选出n个整数，要求等概率。

解法：和洗牌的算法类似，每次随机抽出一个数，抽n次即可。时间复杂度O(m * n)，空间复杂度O(m)。

代码：

 1 // 18.3 pick m integers randomly from an array of n integer.
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <ctime>
 5 #include <vector>
 6 using namespace std;
 7 
 8 void randomSubset(const vector<int> &src, vector<int> &dst, int m)
 9 {
10     vector<int> v;
11     int i, j;
12     int idx;
13     int n;
14     
15     v = src;
16     n = (int)v.size();
17     dst.resize(m);
18     for (i = 0; i < m; ++i) {
19         idx = rand() % n;
20         dst[i] = v[idx];
21         --n;
22         for (j = idx; j < n; ++j) {
23             v[j] = v[j + 1];
24         }
25     }
26     v.clear();
27 }
28 
29 int main()
30 {
31     int i;
32     int n, m;
33     vector<int> src;
34     vector<int> dst;
35     int cc;
36     
37 
38     cc = 0;
39     while (scanf("%d%d", &n, &m) == 2) {
40         ++cc;
41         srand((unsigned)(time(NULL) * cc));
42         src.resize(n);
43         for (i = 0; i < n; ++i) {
44             src[i] = i;
45         }
46         randomSubset(src, dst, m);
47         for (i = 0; i < m; ++i) {
48             printf((i % 8 == 7 ? "%3d
" : "%3d "), dst[i]);
49         }
50         printf("
");
51     }
52     
53     return 0;
54 }