leetCode 382 链表的随机节点 （水库采样算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetCode 382 链表的随机节点 （水库采样算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含681字，纯文字阅读大概需要1分钟。

内容图文

题目链接：点击查看

题目描述：

给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字。

输入输出：
 

输入：    1->2->3->4->5   输出：    3（在这个样例中，我们有均等的概率得到任意一个节点，比如 3 ）       

题目分析：
? 不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采样：遍历一次链表，在遍历到第 m 个节点时，有 1/m 的概率选择这个节点覆盖掉之前的节点选择。详见如下代码。 ? 代码：

class Solution
{
	ListNode *head;
public:
	Solution(ListNode*n):head(n){};
	int getRandom()
	{
		int ans=head->val;
		ListNode *node=head->next;
		int i=2;
		while(node)
		{
			if((rand()%i)==0)//1/i的概率生成随机数0 模拟水库算法中要求的1/i概率 
			{
				ans=node->val;
			}
			++i;
			node=node->next;
		}
		return ans;
	}
};

 

?

内容总结

以上是互联网集市为您收集整理的leetCode 382 链表的随机节点 （水库采样算法）全部内容，希望文章能够帮你解决leetCode 382 链表的随机节点 （水库采样算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---