382. 链表随机节点
-
蓄水池算法:
-
描述:样本总数未知,从所有样本中抽取若干个,要求每个样本被抽到的概率相等
-
算法:从前往后处理每个样本,第i个样本覆盖当前结果的概率为 \(\frac{1}{i}\) , 返回最后结果即为抽样结果
-
证明:证明每个样本最终被抽到的概率相同:
设共n个样本,第 i 个样本被返回的概率为:可见每个样本被抽到概率相同
-
\[P(i) = \frac{1}{i} * (\frac{i}{i + 1} * \frac{i + 1}{i + 2} * ... * \frac{n - 1}{n}) = \frac{1}{n}
\]
\]
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;
};
原文链接: https://www.cnblogs.com/Ivessas/p/15810278.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/185978
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!