leetcode 随机采样

本文包括

  • 382. Linked List Random Node
  • 528. Random Pick with Weight
  • 蓄水池抽样

382. 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:

题目地址: leetcode Linked List Random Node

题意: 给定一个链表,要求以相等的概率返回链表上的结点。

思路:

若已知链表长度len,那么直接随机一下0~len-1,然后遍历到那个结点。

如果不知道长度呢?

我们实时的计算当前遍历了多少个元素cnt,然后以 1/cnt 的概率选择 当前的元素,直到遍历完链表。

这样遍历一遍即可。

为啥是对的?

我们以第2个数为例(就是head.next.val)

选取的概率为(1/2)* (2/3)*(3/4)* ……….. (n-1) / n = 1/n   (选取第2个数在长度为2的时候为1/2,其他的都不要选)

而对于任意的第x数,由于可以覆盖前面的数,均有:\( \frac{1}{x}\times \frac{x}{x+1} \times … \times \frac{n-1}{n} = \frac{1}{n}\)

第n个数就直接1/n啦

大家都是1/n~

 

C++

Java

Python

注:在代码实现上,这里的cnt 比上面讲解中的cnt 少1   randint(x,y)返回的为[x,y]的闭区间。

 

528. Random Pick with Weight

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

  1. 1 <= w.length <= 10000
  2. 1 <= w[i] <= 10^5
  3. pickIndex will be called at most 10000 times.

Example 1:

Example 2:

题目地址: leetcode Random Pick with Weight

题意: 给定一个数组表示下标对应的权重,要求按这个权重数组随机的抽样。(抽样的概率和权重成正比)

思路:

假设没有权重的时候给定n个数就只需要从这n个数随机抽一个即可,每个的概率是1/n。

那么有权重的时候的区别是什么呢?权重为w其实可以看成一个数重复w次,这样随机抽取,抽到的概率就是1/所有权重之和,由于一个数重复w次,因此一个数被抽到就是w/所有权重之和。

代码实现上,可以算到当前数的权重和,然后用二分查找。

Python

 

蓄水池抽样

如果要从n个数中,等概率的抽取k个数呢?

这是蓄水池抽样算法,伪代码如下

即个数<k的时候直接放入,当做水池。

从k + 1开始,第i个数,每个数以 k / i的概率被选中,并随机的替换蓄水池的k个数中的一个,这样每个数的概率都是k / n

证明如下:

第i个数(i > k)最后被选中的概率 = 第i个数时以概率 k / i被选中,之后的数不被选中或者选中的不替换第i个数\[
\frac{k}{i} * [(1- \frac{k}{i + 1} + \frac{k}{i + 1}\times\frac{k-1}{k}) \times (1- \frac{k}{i + 2} + \frac{k}{i + 2}\times\frac{k-1}{k})\times… \times (1- \frac{k}{n} + \frac{k}{n}\times\frac{k-1}{k})] \\=
\frac{k}{i} \times (\frac{i}{i + 1} \times \frac{i + 1}{i + 2} \times … \times \frac{n – 1}{n} ) = \frac{k}{n}
\]

而对于前k个数,类似的也有\[
(1- \frac{k}{k + 1} + \frac{k}{k + 1}\times\frac{k-1}{k}) \times (1- \frac{k}{k + 2} + \frac{k}{k + 2}\times\frac{k-1}{k})\times… \times (1- \frac{k}{n} + \frac{k}{n}\times\frac{k-1}{k}) \\=
\frac{k}{k + 1} \times \frac{k + 1}{k + 2} \times … \times \frac{n – 1}{n} = \frac{k}{n}
\]
本题是leetcode 382 Linked List Random Node 的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 随机采样
本文地址:https://www.hrwhisper.me/leetcode-random-sample-from-array-or-linked-list/

听说长得好看的已经打赏了

Leetcode , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *