LC382-链表随机节点

382. 链表随机节点

• 蓄水池算法：

  • 描述：样本总数未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等

  • 算法：从前往后处理每个样本，第i个样本覆盖当前结果的概率为 \(\frac{1}{i}\) , 返回最后结果即为抽样结果

  • 证明：证明每个样本最终被抽到的概率相同：

    设共n个样本，第 i 个样本被返回的概率为：可见每个样本被抽到概率相同

class Solution {
public:
    Solution(ListNode* head) {
        H = head;
    }
    
    int getRandom() {
        int i = 1, res = -1;
        for(auto p = H; p; p = p->next, ++i)
            if(rand() % i == 0) res = p->val;
        return res;
    }
    ListNode* H;
};