首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目3
《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\n" : "%3d "), dst[i]); 49 } 50 printf("\n"); 51 } 52 53 return 0; 54 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。