|
本题为给定一个单向链表，返回其中任意一个结点val的值
比较直观的一种做法是，先确定链表的长度n，然后随机一个[0,n)之间的整数randomN，用循环迭代randomN次即可
但是题干中提示链表的长度可能特别的大，所以很难确定链表的长度，进而上述方法不能使用
这道题的解决需要用到概率论的知识。即蓄水池抽样思想，当random(0,n) = 0时，用第n+1个值做返回值，下面给出证明
1、当链表长度为1时，抽到第一个元素的概率为1
2、假设抽取前n个元素的概率相等，均为1/n
3、当抽取第n+1个元素时，若random(0,n) = 0, 则用第n+1个元素替换返回值，其概率为1/(n+1);否则则返回前n个值中的某一个值，对每个值来说，其概率为(1-1/n+1)*1/n = 1/n+1，仍为等概率抽取
给出解题代码：
class Solution {
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
p = head;
}
/** Returns a random node's value. */
int getRandom() {
ListNode *tmp = p;
int val;
for(int i = 1; tmp != NULL; i++){
if(random() % i == 0) val = tmp->val;
tmp = tmp->next;
}
return val;
}
private:
ListNode *p;
};
| 
转播
