@(LeetCode)
问题描述
给定一个单链表，返回链表中随机节点的值。每个节点必须有相同的几率被选中。
如果链表非常大，并且它的长度未知？如何不使用额外空间来解决这个问题？
栗 1：
链表： 1->2->3
通过 getRandom 方法返回随机节点值，即 1,2,3 中任意一个，且概率相同。
解题思路
我的解法
这种方式其实与题意不太符合，需要遍历 2 次。
首先计算出链表的长度 N，然后通过 random 方法得到 [0, N-1] 之间的一个随机数 x，从头遍历 x+1 个节点即达到随机的节点。
var Solution = function(head) {
this.head = head
let length = 0
while (head) {
length += 1
head = head.next
}
this.length = length
};
/**
* Returns a random node's value.
* @return {number}
*/
Solution.prototype.getRandom = function() {
if (this.length > 0) {
const random = Math.floor(Math.random() * this.length)
let i = 0
let node = this.head
while (i < random) {
node = node.next
i += 1
}
return node.val
}
};
其他解法
理论基础
因为链表长度未知，可以认为它是动态变化的。即在总数 n 变化时，仍保持选中一个数的概率为 1/n。
即需满足如下条件：
- 当有
k个数，任意选择一个数的概率为1/k； - 当有
k+1个数，任意选择一个数的概率为1/(k+1)，也就是之前已选中的数的概率也变为1/(k+1)； - 当有
k+i个数，任意选择一个数的概率为1/(k+i)，也就是之前已选中的数的概率也变为1/(k+i)。
推导过程
我们可以试着从以下简单的场景来了解。
假设有一个数组，其长度是动态变化的。
- 初始值为
[1]，显然选择一个数的概率为1。 - 当数组变成
[1,2]，选择一个数的概率为1/2，那么选择2的概率为1/2。 - 当数组变成
[1,2,3]，显然选择3的概率为1/3，那么仍选择2的概率为多少呢？根据上面的结论，要为1/3才对。
根据逻辑思维推导：「这一步仍选 2」 = 「这一步不选 3」 并且「上一步选 2」。
用数学公式表示为：p(这一步仍选 2) = p(上一步选 2) * p(这一步不选 3)
显然，p(这一步不选 3) = 1- p(这步选 3)。
则得出： p(这一步仍选 2) = p(上一步选 2) * (1 - p(这步选 3))。
代入数值得到：p(这一步仍选 2) = 1/2 * (1 - 1/3) = 1/3。
因此，当数组长度变成 3 后，选中 2 的概率变为 1/3，满足结论。
同理，推演到 k 个数。在 k 个数选中一个数 x 的概率为 1/k，那么当有 k+i 个数后，仍选中 x 的概率为：
p = p(上一步选中 x) * p(这一步不选中 k+i) = p(上一步选中 x) * (1 - p(这步选中 k+i))
上一步选中 x ，即在 k+i-1 个数中选一个数，其概率为 1/(k+i-1)，这是前提条件。
很显然，p(这步选中 k+i) = 1/(k+i)。
那么可得出 p = 1/(k+i-1) * (1 - 1/(k+i)) = 1/(k+i)，则保证概率也是相同的。
解题方法
那么知道上述结论后，该题的思路转变如下。
如果目前有 n 个节点，当新增加一个节点，只需要保证该节点被选中的概率为 1/(n+1) 即可。
举个栗子：
若初始数据为 [1]，只能选 1；
新增 2 后，数据变成 [1,2]，那么需保证 2 被选中的概率为 1/2 即可；
新增 3 后，数据变成 [1,2,3]，那么需保证 3 被选中的概率为 1/3。
所以只要根据当前数组的长度 n 取一个随机值 r = [0, n-1]，如果 r 刚好等于 0 或者是 [0, n-1] 中的任意一个数，则表示其概率为 1/n， 这时 x 被替换成新数据。
js 代码如下：
Solution.prototype.getRandom = function() {
let count = 1
let node = this.head
let result
while (node) {
// 生成 [0, count-1] 的随机数
const random = Math.floor(Math.random() * (count))
// 替换节点
if (random === 0) {
result = node
}
count += 1
node = node.next
}
return result.val
};
Reservoir Sampling
该题其实是 Reservoir Sampling 水塘抽样算法的简化版。该算法保证了数据总数在变化时，仍能等概率抽取数据。基本思想如下：
- 首先从
n个数中取k个数放入水池中，每个数被选中的概率为k/n。 - 在处理第
n+1个数时，已经在水池中的k个数被选中的概率变为k/(n+1)。 - 在处理第
n+i个数时，已经在水池中的k个数被选中的概率变为k/(n+i)。
推导过程
如果在 n 中选中了 k 个数分别为 [x, y, z, ...]，每个数选中的概率为 k/n。
那么当为 n+1 个数时，x 仍被选中的概率为多少呢？即上一步保留 x 且这一步也保留 x。
那么数学公式如下：
p(x) = p(上一步选择了 x) * p(这步「第 n+1 个数不替换 x」)
p(x) = p(上一步选择了 x) * p(1 -「这步选第 n+1 个数」且「替换 x」)
其中，已知条件如下：
p(上一步选择了 x) = k/n
p(这步选第 n+1 个数) = k/(n+1)
但「第 n+1 个数替换掉 x 」的概率是多少呢？因为只选 k 个数，在 k 个数中替换掉 1 个，其概率为 1/k。
则我们可以得到：p(x)= k/n * (1 - k/(n+1) * 1/k) = k/(n+1)，满足结论。
令 k = 1 则为题目中的问题。
重点
所以最为重要的是保证第 n+1 个数被选中的概率为 k/(n+1)。
这里有两种方式保证概率，是等效的。
- 生成
0~1之间的随机数，如果其值< k/(n+1)，则选中第n+1个数放入水池，替换掉其中的一个数。 - 生成
[0, n+1)之间的随机数，如果其值< k，则选中第n+1个数放入水池，替换掉其中的一个数。
其算法代码也比较简单：
// stream 表示数据流
// reservoir 用来存选中的数据
// 先取 k 个数放入水池
for ( int i = 0; i < k; i++)
reservoir[i] = stream[i];
for (i = k; stream != null; i++) {
p = random(0, i);
if (p < k) reservoir[p] = stream[i];
}
以上就是整个的分析过程。
参考链接：
[1] https://www.cnblogs.com/strugglion/p/6424874.html
[2] https://gregable.com/2007/10/reservoir-sampling.html
[3] https://leetcode.com/problems/linked-list-random-node/discuss/85659/Brief-explanation-for-Reservoir-Sampling
网友评论