适用情况

当大量数据位于数据流中，无法一次性读取进内存，未知数据的大小，从中抽取k个数，并且要保证每次抽取的概率相等，这个时候，就适用水塘抽样算法

算法详解

当k=1时

当k=1时，即只抽取一个数

算法：每次只保留一个数，当遇到第 i 个数时，以 $\frac{1}{i} $的概率保留它，$\frac{(i-1)}{i} $的概率保留原来的数。

对于数字1~4，依次读取之，有：

• 读取1时，概率为1，保留1

• 读取2时

  • 保留2的概率概率为$\frac{1}{2} $
  • 保留1的概率为$\frac{2-1}{2} =\frac{1}{2} $

• 读取3时

  • 保留3的概率为$\frac{1}{3} $
  • 保留2的概率：读取2时保留2，本轮保留2，即$\frac{1}{2} \times \frac{3-1}{3} =\frac{1}{3} $
  • 保留1的概率：读取2时保留1，本轮保留1，即$\frac{1}{2} \times \frac{3-1}{3} =\frac{1}{3} $

• 读取4时

  • 保留4的概率为$\frac{1}{4} $
  • 保留3的概率：读取3时保留3，本轮保留3，即$\frac{1}{3} \times \frac{4-1}{4} =\frac{1}{4} $
  • 保留2的概率：读取3时保留2，读取2时保留2，本轮保留2，即$\frac{1}{2} \times \frac{3-1}{3} \times \frac{4-1}{4} =\frac{1}{4} $
  • 保留1的概率：读取3时保留1，读取2时保留1，本轮保留1，即$\frac{1}{2} \times \frac{3-1}{3} \times \frac{4-1}{4} =\frac{1}{4} $

由此可见，每次对先前的数和当前的数的保留概率均相等，满足条件

证明可用数学归纳法，本文略

当k=m时

当k=m时，即抽取m个数，流程与k=1时相似，只需要将每次的概率都乘上m即可

Leetcode 382.链表随机节点

题目描述

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

Solution(ListNode head) 使用整数数组初始化对象。

int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

题解

方法1——使用数组保存节点

保存所有节点到数组，随机抽取

空间复杂度：$O(n)$

时间复杂度：初始化为$O(n)$，随机取数为$O(1)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type Solution struct {
    Arr []int
}

func Constructor(head *ListNode) Solution {
    s := Solution{Arr: make([]int, 0)}
    for head != nil {
        s.Arr = append(s.Arr, head.Val)
        head = head.Next
    }
    return s
}

func (this *Solution) GetRandom() int {
    return this.Arr[rand.Intn(len(this.Arr))]
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(head);
 * param_1 := obj.GetRandom();
 */

结果：

执行用时：12 ms, 在所有 Go 提交中击败了98.25%的用户

内存消耗：7.3 MB, 在所有 Go 提交中击败了9.65%的用户

方法2——水塘抽样算法

使用水塘抽样算法

空间复杂度：$O(1)$

时间复杂度：初始化为$O(1)$，随机取数为$O(n)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
type Solution struct {
    Head *ListNode
}

func Constructor(head *ListNode) Solution {
    s := Solution{Head: head}
    return s
}

func (this *Solution) GetRandom() int {
    node, i := this.Head, 1
    res := node.Val
    for node != nil {
        //从[0,i)取数，取到0的概率为1/i
        if rand.Intn(i) == 0 {
            res = node.Val
        }
        node = node.Next
        i++
    }
    return res
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(head);
 * param_1 := obj.GetRandom();
 */

结果：

执行用时：16 ms, 在所有 Go 提交中击败了74.56%的用户

内存消耗：7.2 MB, 在所有 Go 提交中击败了40.35%的用户