1.链表以等概率的方式随机返回节点

/**
 * 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:
    Solution(ListNode* head) {
        this->node = head;

    }
    
    int getRandom() {
        int count = 1;
        int ans = 0;
        while(node) {
            if (random()%count == 0) {
                ans = node->val;
            }
            ++count;
            node = node->next;
        }
        return ans;
    }
private:
    ListNode* node;
};

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

2.等概率选择K个节点

for(int i = 0; i < k; ++i)
  R[i] = L[i];
for(int i = k; i < n; ++i) {
  j = rand.nextInt(i+1);
  if(j < k)
    R[j] = L[i];
}
return R;

3.分布式 https://ballsandbins.wordpress.com/2014/04/13/distributedparallel-reservoir-sampling/

假设存在A和B两条数据流，A的长度为m，B的长度为n，且m和n都远大于k。
可以使用问题2中的采样算法分布得到R和S，接下来要考虑如何融合R和S。
假设选择R的概率p=m/(m+n)，反之不选择的概率为1-p。
可以得出选择R的概率为 1/k*k/m * m/(m+n) = 1/(m+n)

for(sub-stream s: sub-streams) do in parallel {
  simple sequential reservoir sampling and count length of s;
}
double p = (double) m / (m+n);
for(int i = 0; i < k; ++i){
  j = rand.nextDouble();
  if(j <= p)
    move a random item from R to T;
  else
    move a random item from S to T;
}
return T;