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

[eastphoton]

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

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

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

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

[stein42]

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

```
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)
```

[virusdefender]

special judge 吧，也就是写一段代码来判断，各种 oj 都有这功能

[SingeeKing]

咱就说，有没有一种可能，他是跑了你的代码然后检查输入输出

[SingeeKing]

哦不我看错了，忽略我…

[adjusted]

random 设置下 seed 吧

[wy315700]

special judge 写一段代码来检测你的输出的，写 oj 的时候经常用到的，除了随机数算法，一些涉及浮点数的可能也要用到