一直很好奇 leetcode 是怎么判断随机算法的正误的

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 660 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如今天的每日一题： https://leetcode.cn/problems/random-pick-with-blacklist/，还有这些： https://leetcode.cn/tag/randomized/problemset/

毕竟随机结果没法直接对比标准答案，感觉要判断正误就挺麻烦，但 leetcode 可以测出来正确性。

有时候写出来某个细节差个+1 -1 ，那概率分布也差不太多吧，它也能测出来有错误不给 AC 。感觉就挺神奇的。

没有搜到有对这个的讨论。。

6 条回复 • 2022-06-26 20:16:43 +08:00

stein42

2022-06-26 14:59:42 +08:00

应该是用统计学里的假设检验来验证，这里是离散均匀分布，可以用皮尔森卡方检定。
假设检验本身就可能犯第一类错误（拒绝正确结果）和第二类错误（接受错误结果）。
我试过，轻微改变分布还是能通过。

```
import bisect
import random

class Solution:
....def __init__(self, n: int, blacklist: List[int]):
........self.m = n - len(blacklist)
........self.ss = [a - i for i, a in enumerate(sorted(blacklist))]

....def pick(self) -> int:
........r = random.randrange(self.m)
........return r + bisect.bisect_right(self.ss, r)
```

```
import bisect
import random

class Solution:
....def __init__(self, n: int, blacklist: List[int]):
........self.m = n - len(blacklist)
........self.ss = [a - i for i, a in enumerate(sorted(blacklist))]

....def pick(self) -> int:
........if random.random() < 1 / (100 * self.m):
............r = 0
........else:
............r = random.randrange(self.m)
........return r + bisect.bisect_right(self.ss, r)
```