应用场景：大数据流中的随机抽样问题。 即：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。

数学证明

采样策略策略

  • 对于前k个数，我们全部保留。
  • 对于第i（i>k）个数，我们以水塘抽样 - 图1的概率保留第i个数，并以 水塘抽样 - 图2的概率与前面已选择的k个数中的任意一个替换。
    1. vector<int> ReservoirSampling(vector<int>& results, vector<int>& nums, int k)
    2. {
    3.   vector<int> results(k);
    4.   int n = nums.size();
    5.   // 对于前k个数，我们全部保留
    6.   for (int i = 0; i < k; ++i) {
    7.       results[i] = nums[i];
    8.   }
    9.   // 后面的数据，进行替换
    10.   for (int i = k; i < n; ++i) {
    11.       int random = rand() % i;
    12.       if (random < k) {
    13.           results[random] = nums[i];
    14.       }
    15.   }
    16.   return results;
    17. }
    18. // 时间复杂度O(n);

随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

  1. class Solution {
  2.     vector<int> &nums;
  3. public:
  4.     Solution(vector<int> &nums) : nums(nums) {}
  6.     int pick(int target) {
  7.         int ans;
  8.         for (int i = 0, cnt = 0; i < nums.size(); ++i) {
  9.             if (nums[i] == target) {
  10.                 ++cnt; // 第 cnt 次遇到 target
  11.                 if (rand() % cnt == 0) {
  12.                     ans = i;
  13.                 }
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. };
  19. // pick时间复杂度O(n)