蓄水池抽样算法

算法概述

  • 蓄水池抽样算法描述了这样一个场景：从一个总量未知的数据集中，抽取一定数量的样本，使得每个样本数量被抽到的概率是相同的。

  • 我们对上述过程进行抽象，我们假设数据集的总量是n，最后抽取m个样本。我们需要保证每个样本被抽到的概率是m/n。

    算法步骤

  • 由于数据集的总量n未知，我们依次针对每个样本来进行操作。

  • 对于前面m个样本，我们直接放入样本池。
  • 对于第m + 1个元素，我们令它被抽取的概率为m/(m + 1)。对于样本池的某个样本来说，该次被该样本保留的概率=上次保留的概率这次保留的概率=1(当前元素未被选中的概率+当前元素被选中，但是样本未被替换的概率) = 1(1/(m + 1) + m/(m + 1) (m - 1)/m) = m/(m + 1)。因此，至此，每个样本被保留的概率都是m/(m+1)。
  • 对于第m + 2个元素，我们令它被抽取的概率为m/(m + 2)。对于样本池的某个样本来说，该次被该样本保留的概率=上次保留的概率这次保留的概率=1(当前元素未被选中的概率+当前元素被选中，但是样本未被替换的概率) = m/(m + 1) (2/(m + 2) + m/(m + 2) (m - 1)/m) = m / (m + 2)。因此，至此，每个样本被保留的概率都是m/(m+2)。
  • …
  • 对于第m + k个元素，我们令它被抽取的概率为m/(m + k)。对于样本池的某个样本来说，该次被该样本保留的概率=上次保留的概率这次保留的概率=1(当前元素未被选中的概率+当前元素被选中，但是样本未被替换的概率) = m / (m + k - 1) (k/(m + k) + m/(m + k) (m - 1)/m) = m / (m + k)。因此，至此，每个样本被保留的概率都是m/(m+k)。

  • 由此可见，对于每个元素来说，对于同样大小的数据集合，被抽到的概率都是m/n。

    Linked List Random Node

    题目描述

    Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
    Follow up:
    What if the linked list is extremely large and its length is unknown to you?
    Could you solve this efficiently without using extra space?

    题目解析

    此题是蓄水池算法m=1的特殊情况。 ```cpp /**

    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • ListNode *next;
    • ListNode() : val(0), next(nullptr) {}
    • ListNode(int x) : val(x), next(nullptr) {}
    • ListNode(int x, ListNode *next) : val(x), next(next) {}

    • }; / class Solution { public: /* @param head The linked list’s head.

      1. Note that the head is guaranteed to be not null, so it contains at least one node. */

      int cnt; ListNode* head;

      Solution(ListNode* _head) {

      head = _head;

      }

      /* Returns a random node’s value. / int getRandom() {

      int ans;
cnt = 0;
for (ListNode * p = head; p; p = p->next) {
    cnt ++;
    // rand() produce a num in range [0, cnt - 1]
    if (rand() % cnt == 0) {
        ans = p->val;
    }
}
return ans;

      } };

/**

  • Your Solution object will be instantiated and called as such:
  • Solution* obj = new Solution(head);
  • int param_1 = obj->getRandom(); */ ```