Saturday, December 1, 2018

[Summary]Random


Fisher Yates Algorithm

洗牌算法,O(n)时间生成一个random的排列。

讲解:
Fisher Yates

例题:
Shuffle an Array 解答

Reservoir Sampling Algorithm

给定一个数据流,在我们不知道长度的情况下,需要取k个随机的数据。Reservoir Sampling可以帮助我们在O(n)的时间解决这一题。

讲解:
Reservoir Sampling

例题:
Linked List Random Node 解答
Random Pick Index 解答

每次和末尾交换保证连续的区间

在一个区间内不停地取随机数并且删除可以用这种方法。

例题:
Insert Delete GetRandom O(1) 解答
Insert Delete GetRandom O(1)-Duplicates allowed 解答
Random Flip Index 解答
Random Pick with Blacklist 解答

带权值的随机数

基本思路是presum + binary search

例题:
Random Pick with Weight 解答
Random Point in Non-overlapping Rectangles 解答

Inverse Transform Sampling

概率分布函数(PDF)->累积分布函数(CDF)->Inverse CDF

例题:
Generate Random Point in a Circle 解答

用小的randX()实现更大的randY()

本质上是进制问题,用randX()生成比Y大的randZ()即可

例题:
Implement Rand10() Using Rand7() 解答

No comments:

Post a Comment