k*******t
发帖数: 144 | 1 raffle题，pick winner with equal probabilities。要实现如下两个函数，一个void
acceptEntry(Entry e), 另一个Entry pickWinner()。 如何实现in constant space? |
c**1
发帖数: 71 | 2 int count=0;
Entry result = null;
void acceptEntry(Entry e) {
++count;
if (randomLessThan(count) == 0) {
result = e;
}
}
Entry pickWinner() {
return result;
} |
k*******t
发帖数: 144 | 3 能否详细说下里面的if语句后面的原理，怎么保证equal propobility? 抛个link也可
以。
if (randomLessThan(count) == 0) {
result = e;
}
【在 c**1 的大作中提到】
: int count=0;
: Entry result = null;
: void acceptEntry(Entry e) {
: ++count;
: if (randomLessThan(count) == 0) {
: result = e;
: }
: }
: Entry pickWinner() {
: return result;
|
a********m
发帖数: 15480 | 4 这题目不知道答案的话还是挺难想到的。
a： 1/1 = 100%
b： 1/2 机会替换。a的概率是1/2
c： 1/3 机会替换。a的概率是2/3*1/2=1/3,b相同
... |
k*******t
发帖数: 144 | 5 哎，还是不明白啊
【在 a********m 的大作中提到】
: 这题目不知道答案的话还是挺难想到的。
: a： 1/1 = 100%
: b： 1/2 机会替换。a的概率是1/2
: c： 1/3 机会替换。a的概率是2/3*1/2=1/3,b相同
: ...
|
