18.3 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.
这道题让我们从一个数组中随机取出m个数字，要求每个数字被取出的概率相同，其实这道题用的是之前那道18.2 Shuffle Cards的方法，同样我们可以用递归和迭代两种方法来做，递归的思路还用的回溯法，回溯到i+1==m的时候，取出数组中前m个数字放到结果res中，然后一层一层的返回，返回的过程中每次在[0, i]之间取出一个随机数，然后如果这个数小于m，那么更新res[k]的值为nums[i]，这样相当于一种洗牌，这样保证了每个数被取出的概率都相同，参见代码如下：
解法一：
vector<int> pick(vector<int> &nums, int m, int i) { if (i + 1 < m) return {}; else if (i + 1 == m) { vector<int> res(m); for (int k = 0; k < m; ++k) { res[k] = nums[k]; } return res; } else { vector<int> res = pick(nums, m, i - 1); int k = rand() % (i + 1); if (k < m) res[k] = nums[i]; return res; } }
当然还有对应的迭代的写法，思路都一样：
解法二：
vector<int> pick(vector<int> &nums, int m) { vector<int> res(m); for (int i = 0; i < m; ++i) { res[i] = nums[i]; } for (int i = m; i < nums.size(); ++i) { int k = rand() % (i + 1); if (k < m) res[k] = nums[i]; } return res; }
本文转自博客园Grandyang的博客，原文链接：随机生成数字[CareerCup] 18.3 Randomly Generate Integers ，如需转载请自行联系原博主。
