水塘抽样是动态等概率抽样。用来从一集合中随机且等概率地抽取K个元素。

    • Leetcode 382

      给你一个未知长度的链表，请你设计一个算法，只能遍历一次，随机地返回链表中的一个节点。

    1. int getRandom(ListNode* head){
    2.      int ret=0;
    3.     ListNode* cur=head;
    4.     int i=1;
    5.     while(cur!=nullptr){
    6.          if(rand()%i==0){
    7.              ret=cur->val;   
    8.         }
    9.         i++;
    10.         cur=cur->next;
    11.     }
    12.     return ret;
    13. }
    • Leetcode 392

    给定一个可能含有重复元素的整数数组，要求随机输出一个给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

    int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums);

    // pick(3) 应该返回索引 2,3 或 4。每个索引的返回概率应该相等。

    solution.pick(3);

    // pick(1) 应该返回 0。因为只有nums[0]等于1。

    solution.pick(1);

    1. #include<utility>
    2. class Solution {
    3. public:
    4.     vector<int> arr;
    5.     Solution(vector<int>& nums) {
    6.         arr=std::move(nums);
    7.     }
    9.     int pick(int target) {
    10.         int ret=0;
    11.         int count=0;
    12.         for(int i=0;i<arr.size();++i){
    13.             if(arr[i]==target){
    14.                 count++;
    15.                 if(rand()%count==0){
    16.                     ret=i;
    17.                 }
    18.             }
    19.         }
    20.         return ret;
    21.     }
    22. };
    • 在N个数的数组中等概率地随机选取K个数（抽奖问题）
      1. vector<int> getRandom(vector<int>& arr, int k){
      2.   vector<int> ret;
      3.   for(int i=0;i<k;++i){
      4.        ret.emplace_back(arr[i]);   
      5.   }
      6.   for(int i=k;i<arr.size();++i){
      7.       int j=rand()%i;
      8.       if(j<k){
      9.            ret[j]=arr[i];   
      10.       }
      11.   }
      12.   return ret;
      13. }
      这里的时间复杂度是O(N)，即从30W的人中抽10W人仍需进行30W次的计算。
      有没有更低时间复杂度的策略？有的，下面的抽奖方式就是：
      1. vector<int> getRandom(vector<int> arr, int k){
      2.   vector<int> ret;
      3.   int size=arr.size();
      4.    for(int i=0;i<k;++i){
      5.        int randInx=rand()%(size-i)+i;
      6.       swap(arr[randInx],arr[i]);
      7.   }
      8.   for(int i=0;i<k;++i){
      9.        ret.emplace_back(arr[i]);   
      10.   }
      11.   return ret;
      12. }
      这种抽奖方式的时间复杂度是O(k)，但是拥有更高的空间复杂度，空间复杂度为O(N).