目录:

随机化
- Python 随机数速查模板

预计阅读时间：15 分钟

随机化

随机化题的难点通常不在代码，而在「为什么每个结果的概率真的相等」。代码往往只有十来行，写错一个下标范围，分布就悄悄歪掉，样例还照样能过——判题器至多做统计检验，样例过了不代表分布对，自己肉眼更看不出来。所以这类题我的习惯是：先拿 n = 2、3 这种小数把概率一项项乘出来，乘对了再写代码。

本合集收录随机化类题目：$O(1)$ 增删 + 随机取（380、381）、按权重随机（528）、链表随机节点 / 蓄水池（382、398）、洗牌（384）、用 rand7 造 rand10（470）等题型。先放一节 Python 随机数速查模板，题目小节随训练进度补上。

Python 随机数速查模板

API 速查

最容易记混的是端点：randint 两端都含，randrange 跟 range 一样左闭右开。

import random

random.randint(1, 6)          # int in [1, 6], BOTH ends inclusive
random.randrange(0, n)        # int in [0, n), like range(); step allowed: randrange(0, 10, 2)
random.random()               # float in [0.0, 1.0)
random.uniform(a, b)          # float between a and b (b may or may not appear, float rounding)

random.choice(seq)            # one element; seq must support indexing (list/str/tuple)
# random.choice({1, 2, 3})    # TypeError: 'set' object is not subscriptable
# random.sample({1, 2, 3}, 2) # TypeError since 3.11: population must be a sequence
# list(s) works but costs O(n) per call -- keep a list alongside the set instead (see 380)

random.choices(seq, weights=[1, 3], k=5)  # k picks WITH replacement, weighted; len(weights) must equal len(seq), else ValueError
random.sample(seq, k)         # k distinct positions, WITHOUT replacement
random.shuffle(lst)           # in place, returns None -- never write lst = random.shuffle(lst)
random.seed(42)               # fix the sequence for local debugging only

几条实战提醒：

choice 要能下标访问。题目让你「从集合里随机取一个」时，不能对 set 直接 choice，每次 list(s) 又是 $O(n)$，这正是 380 要额外维护一个数组的原因。
三个名字这样记：choice 取一个；choices 多一个 s，取 k 个，有放回、可带权；sample 取 k 个，无放回（k 个位置互不相同）。真正容易看错的是 choice 和 choices，只差一个 s，一个返回单个元素，一个返回列表。
shuffle 原地修改、返回 None，a = random.shuffle(a) 会把 a 变成 None。
面试官常要求手写（384 不调 shuffle、528 不调 choices）。下面五个模板里，模板二、模板四分别是 shuffle、choices（带权）背后的做法，其余三个是常考的结构 / 采样技巧。

模板一：列表 O(1) 插入 / 删除 / 随机取

什么时候用：要同时支持 $O(1)$ 插入、$O(1)$ 删除、$O(1)$ 等概率随机取。对应 380。

随机取要求下标访问，所以元素存在数组里；但数组中间删除是 $O(n)$。办法是把要删的元素和末尾元素交换，再 pop 末尾，再配一个「值 → 下标」的哈希表找位置。

先拿具体数走一遍：arr = [5, 8, 2]，pos = {5: 0, 8: 1, 2: 2}，删除 8：

idx = pos[8] = 1，末尾元素 last = 2；
arr[1] = 2，pos[2] = 1（被搬过来的末尾元素换了位置，下标要跟着改）；
arr.pop() 得 arr = [5, 2]，del pos[8] 得 pos = {5: 0, 2: 1}。

def insert(self, val):
    if val in self.pos:
        return False
    self.pos[val] = len(self.arr)   # index of the slot about to be appended
    self.arr.append(val)
    return True

def remove(self, val):
    if val not in self.pos:
        return False
    idx = self.pos[val]
    last = self.arr[-1]
    self.arr[idx] = last
    self.pos[last] = idx   # update the moved element first
    self.arr.pop()
    del self.pos[val]      # delete last: correct even when val is the tail itself
    return True

def getRandom(self):
    return self.arr[random.randrange(len(self.arr))]

坑：顺序。 要删的恰好就是末尾元素时，last == val。正确顺序下 self.pos[last] = idx 会先把 pos[val] 写成它自己的下标，随后 del pos[val] 把它删掉，结果正确。如果先 del pos[val] 再 pos[last] = idx，就会把已删掉的 key 又写回哈希表，之后 insert(val) 会误判「已存在」。所以记住：先改被搬来的末尾元素的下标，最后再 pop 和 del。

扩展到 381：381 允许重复值，「值 → 单个下标」不能直接套（同一个值会有好几个下标）。要把 pos 改成「值 → 下标集合（set）」：删除时用 idx = pos[val].pop() 取出并删掉一个下标，照样把末尾元素 last 搬到 idx，再同步改 last 自己那个集合：先 pos[last].add(idx)，再 pos[last].discard(len(arr) - 1)，最后 pop 末尾；若 pos[val] 空了就 del pos[val]。

def remove(self, val):             # self.pos = defaultdict(set)
    if val not in self.pos:
        return False
    idx = self.pos[val].pop()      # take out one index of val
    last = self.arr[-1]
    self.arr[idx] = last
    self.pos[last].add(idx)        # add first ...
    self.pos[last].discard(len(self.arr) - 1)   # ... then drop the tail index
    self.arr.pop()
    if not self.pos[val]:
        del self.pos[val]
    return True

这个「先 add 再 discard」的顺序在 idx 恰好就是末尾时也正确：此时 last == val，add(idx) 把刚取出的下标加回去，紧接着 discard 又把它删掉。反过来先 discard 再 add，就会把末尾这个已经不存在的下标留在集合里。

模板二：Fisher-Yates 洗牌

什么时候用：要等概率生成一个随机排列，不能调 shuffle。对应 384。

def shuffle(self):
    a = self.nums[:]                     # copy, keep the original for reset()
    for i in range(len(a) - 1, 0, -1):   # i = n-1 down to 1
        j = random.randint(0, i)         # j in [0, i], i itself included
        a[i], a[j] = a[j], a[i]
    return a

为什么对：从后往前，每一步从「还没定下来的前 i+1 个」里等概率挑一个放到位置 i。最后一格有 n 种选法，倒数第二格 n-1 种……任一指定排列出现的概率是 $\frac{1}{n} \times \frac{1}{n-1} \times \cdots \times 1 = \frac{1}{n!}$，恰好均匀。

错误写法：从前往后，共 n 步，每步从整个数组挑。

for i in range(n):
    j = random.randint(0, n - 1)   # WRONG: picks from the whole array every step
    a[i], a[j] = a[j], a[i]

这样 n 步共有 $n^n$ 种等可能的 j 序列，要平均分给 $n!$ 个排列，只有 $n!$ 整除 $n^n$ 才可能均匀。拿 n = 3 算：$3^3 = 27$ 种结果分给 $3! = 6$ 个排列，27 不是 6 的倍数，必然分不匀。我按上面这个循环把 [1, 2, 3] 的 27 种 j 序列全部枚举了一遍，统计洗牌后的结果数组：(1,3,2)、(2,1,3)、(2,3,1) 各出现 5 次，(1,2,3)、(3,1,2)、(3,2,1) 各 4 次，概率是 5/27 对 4/27。

另一个坑是 j 的上界是 i 而不是 i-1：把正确模板里的 randint(0, i) 写成 randint(0, i - 1)（这叫 Sattolo 算法），每个元素都不可能留在原位，只会产生 $(n-1)!$ 个「转一整圈」的排列。n = 3 时只剩 (2,3,1)、(3,1,2) 两种，同样不均匀。

模板三：蓄水池抽样（抽 k = 1 个）

什么时候用：数据是流或链表，长度事先不知道（或不想先数一遍、不想 $O(n)$ 额外空间），要等概率取一个。对应 382（链表随机节点）、398（随机返回目标值的某个下标）。

def getRandom(self):
    ans = None
    i = 0
    node = self.head
    while node:
        i += 1
        if random.randint(1, i) == 1:    # replace with probability 1/i
            ans = node.val
        node = node.next
    return ans

先拿流 [a, b, c] 走一遍，看 a 最后被留下的概率：

第 1 个：randint(1, 1) == 1 必成立，a 入选，概率 1；
第 2 个：b 以 1/2 替换，a 留下的概率 1/2；
第 3 个：c 以 1/3 替换，a 留下的概率 2/3。

a 最终留下的概率 $1 \times \frac{1}{2} \times \frac{2}{3} = \frac{1}{3}$。一般地，第 i 个元素被选中的概率是 $\frac{1}{i}$，之后每一步都不被替换的概率是 $\frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{n-1}{n}$，连乘相消等于 $\frac{i}{n}$；再乘上它被选中的 $\frac{1}{i}$，得 $\frac{1}{i} \times \frac{i}{n} = \frac{1}{n}$，与 i 无关。

398 只是把「每个节点」换成「每个等于 target 的下标」：遍历下标 j，只在 nums[j] == target 时计数 i 加一并按 1/i 替换。

模板四：按权重随机

什么时候用：下标 i 被选中的概率要等于 $\frac{w_i}{\sum w}$，且要查询多次。对应 528。

做法是前缀和 + 二分：把每个下标看成数轴上一段长度为 $w_i$ 的区间，在 $[1, total]$ 里均匀取一个整数 r，落在哪段就返回哪个下标，也就是找第一个 pre[i] >= r 的位置。

def __init__(self, w):
    self.pre = []
    s = 0
    for x in w:
        s += x
        self.pre.append(s)

def pickIndex(self):
    pre = self.pre
    r = random.randint(1, pre[-1])       # integer in [1, total], both ends inclusive
    l, h = 0, len(pre) - 1
    while l <= h:
        mid = (l + h) // 2
        if pre[mid] >= r:
            h = mid - 1
        else:
            l = mid + 1
    return l

用 w = [1, 3] 走一遍：pre = [1, 4]，r 等概率取 1、2、3、4。

r = 1：第一个 >= 1 的是 pre[0]，返回下标 0；
r = 2, 3, 4：pre[0] = 1 不够，第一个 >= r 的是 pre[1] = 4，返回下标 1。

下标 0 拿到 1 个值、下标 1 拿到 3 个值，概率 1/4 与 3/4，正好等于权重比。这里 r 必须从 1 开始：若写成 randint(0, total)，r = 0 也会落到下标 0，四个值变成五个，分布就歪了。

模板五：拒绝采样

什么时候用：手里只有一个小范围的均匀随机源，要造出另一个范围的均匀随机数。对应 470（用 rand7 实现 rand10）。

def rand10(self):
    while True:
        idx = (rand7() - 1) * 7 + rand7()   # uniform over 1..49
        if idx <= 40:
            return (idx - 1) % 10 + 1       # 40 values -> 1..10, 4 each
        # 41..49: reject and roll again

为什么 idx 在 1..49 上均匀：rand7() - 1 取 0..6 决定「第几行」，第二个 rand7() 取 1..7 决定「第几列」，49 个格子一一对应 49 种等可能的 (行, 列) 组合，每个概率 1/49。注意不能用 rand7() + rand7()，那是 2..14 且中间值更容易出现，不均匀。

为什么只收 <= 40 而不收全部 49 个：49 除以 10 余 9。若全收，1..40 给 1..10 每个数各 4 个格子，剩下 41..49 这 9 个格子又会映射到 1..9，于是 1..9 各 5/49、10 只有 4/49，不均匀。只收 40 个时每个数恰好 4 个格子，条件概率都是 4/40 = 1/10。被拒绝的概率 9/49，期望轮数 49/40，约 1.2 轮、2.45 次 rand7 调用。

一般化：用 randA 造 randB 时，若 A < B，先用 (randA() - 1) * A + randA() 组合成均匀的 $1..A^2$（不够就再乘一层），截到 B 的最大倍数，超出的部分拒绝重来；若 A ≥ B，直接拒绝超出 B 的值即可（每个 1..B 的值条件概率都是 1/B）。

速查表：题面信号 → 模板

题面信号	模板	题号
$O(1)$ 插入 / 删除，还要 $O(1)$ 等概率随机取	数组 + 值→下标哈希，删除时与末尾交换再 pop	380
同上，但允许重复值	数组 + 值→下标集合（`set`），删除时任取一个下标与末尾交换，同步改末尾元素的集合	381
打乱数组，每个排列等概率，不许调库	Fisher-Yates，`j = randint(0, i)`	384
链表 / 数据流，长度未知，等概率取一个	蓄水池抽样，第 i 个以 1/i 替换	382、398
按权重成比例地随机	前缀和 + 找第一个 `pre[i] >= r`	528
只给一个小范围均匀随机源，要造另一个范围	组合成更大的均匀范围 + 拒绝采样	470

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。

云

沉舟侧畔千帆过

随机化

随机化