[LeetCode]382. Linked List Random Node 链表的随机节点

题目地址:

https://leetcode.com/problems/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?

Example:

题目大意:

提供一个单链表,从这个链表中返回一个随机节点的值。每个节点都必须有相同的被选中的可能性。

接着:

如果这个链表足够大,大到你不知道这个值?你能想到不用其他的空间去解决这个问题吗?

(例子代码见上)


 

既然是相同的可能性,那么解法很可能需要使用随机数函数。而据我所知,C 和 C++的随机数需要播种,这很麻烦。所以我就试着使用 Java 去做。因为 Java 的 Math 包里面有一个 random( )成员函数可以直接生成double型的随机数。那么再补一次强制类型转换即可完成。所以我选择用 Java 完成这道题。

之后我看到题目所给的代码中,很奇怪这个 Solution 类中竟然没有数据成员,只有方法。那么这必然导致getRandom( )方法中没有数据进来。那我们必须自己定义一些数据成员完成传值的任务。

我定义了 ListNode 型的成员 Shead ,记作这个链表的头结点存在 Solution 类中,以便让后面getRandom( )方法可以用。

然后我又定义了一个 int 型数字 number ,用以记录这个链表中的数字个数。

最后审了一遍题,他并不要求我的时间空间复杂度。

好的,开始动手。

其中,Solution的构造函数中,第一次那个 while 循环我还多给他做了一步 temp = new ListNode(temp.val)。所以这一步是很多余的。就是因为少了这一步,程序就没有超时,勉勉强强挤了过去。(我发现我自己想的算法,基本都感觉是踩着最慢的速度运行过去的。)Runtime: 143 ms 我运行了143ms,这个成绩讲真很糟糕。

之后通过random( )方法取到了随机数,再通过限制循环次数的 for 循环得到那个节点,最后返回那个节点的 val 值,便大功告成。


好的那么博主的抖机灵时间结束了。我知道我想的算法一直都不是那么美好。查了一发答案。

答案地址:http://blog.csdn.net/qq508618087/article/details/52188179

“(引用)

思路: 一般的来说, 可以先计算出长度, 然后随机一个在长度范围内的值, 走到那里将值返回即可. 但是如果长度无限大, 就无法计算长度了, 这种情况下成为一个水池抽样的算法, 其原理为一个个的对元素取样, 在遍历到每个元素的时候可以有个概率选取, 或者不选取. 因为是随机选取一个数, 所以相当于水池的容量是1. 相对简单一些.

那么如何确保对于每个元素都有相等的概率呢? 这里用到了概率论的知识, 在遍历到第i个数时设置选取这个数的概率为1/i, 然后来证明一下每个数被选到的概率: 对于第一个数其被选择的概率为1/1*(1-1/2)*(1-1/3)*(1-1/4)*…*(1-1/n) = 1/n, 其中(1-1/n)的意思是不选择n的概率, 也就是选择1的概率乘以不选择其他数的概率. 对于任意一个数i来说, 其被选择的概率为1/i*(1-1/(i+1))*…*(1-1/n), 所以在每一个数的时候我们只要按照随机一个是否是i的倍数即可决定是否取当前数即可.

代码如下:

前辈提出了一个蓄水池抽样的算法。经过一番计算,我不得不承认1/i*(1-1/(i+1))*…*(1-1/n)的结果必定为1/n。不过我不能理解的是该程序第行为何要用随机数对 i 取模。最后我的想法是,只是为了筛选一个元素进蓄水池罢了。(有错务必指出谢谢!)

另一个亮点是,Solution的构造函数竟然只存入一个头节点。其实我还是吃了一惊的。因为他们都说尽量不要去算这个链表的元素个数。我想是怕超时吧。