随机算法相关
蓄水池抽样
当你遇到第
i个元素时，应该有1/i的概率选择该元素，1 - 1/i的概率保持原有的选择。同理，如果要随机选择k个数，只要在第i个元素处以k/i的概率选择该元素，以1 - k/i的概率保持原有选择即可。考虑如下问题：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。
当K=1时，即每次只能读取一个数字。
假设数据流含有N个数，我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为 1/N。
那如何保证呢？
先说方案：
每次只保留一个数，当遇到第 i 个数时，以 1/i 的概率保留它，(i-1)/i的概率保留原来的数。怎么以1/i的概率保留呢? 生成[1:i]的随机数，判断随机数是否和i相同即可。
证明：
假设最终成为答案的样本编号为 k，那么 k 成为答案的充要条件为「在遍历到 k 时被选中」并且「遍历大于 k 的所有元素时，均没有被选择（没有覆盖 k）」。
对应事件概率为：
首项 为选中 的概率，后面每项分别为编号为 的样本不被选中的概率。
只要后面不被选中，当前选中的值才不会更改，即一直保留下去。
import random class Solution: def __init__(self, head: ListNode): self.head = head def getRandom(self) -> int: count = 0 reserve = 0 cur = self.head while cur: count += 1 rand = random.randint(1,count) if rand == count: reserve = cur.val cur = cur.next return reserve
如果扩展到，随机选取 k 个节点，那么代码如下：
class Solution: def __init__(self, head: ListNode): self.head = head def getRandom(self) -> int: # 初始选取 k 个节点作为结果 i, cur = 0, self.head res = [] while i < k and cur: res.append(cur.val) cur = cur.next i += 1 i = k while cur: i += 1 rand = random.randint(1,i) if rand < k: res[i] = cur.val cur = cur.next return reserve
经典题目
洗牌算法
num 为原始数组，shuffled为洗牌之后的数组。
思路：每次随机从 num 中不放回的拿一个数字（即拿完之后pop掉）放进 shuffled 数组中。
两种实现方式
def shuffle(self) -> List[int]: shuffled = [0] * len(self.nums) for i in range(len(self.nums)): # 因为self.nums的大小是在不断变化的，所以有点像： # 每次从 这个备选池中选一个数字，所谓当前的结果池 ，同时，把选中的从备选池中的删掉 j = random.randrange(len(self.nums)) shuffled[i] = self.nums.pop(j) self.nums = shuffled return self.nums # 对上面的一种优化。 def shuffle(self) -> List[int]: for i in range(len(self.nums)): j = random.randrange(i, len(self.nums)) self.nums[i], self.nums[j] = self.nums[j], self.nums[i] return self.nums
经典题目
