I think it's not that easy to come up with an idea to use Reservoir Sampling and the proof of correctness can be even harder. :(
I actually bumped into it during..
Proof is okay.
1.Probability of first k items still in reservoir finally is that of never getting chosen in the process:
kth item...k+1th item......nth item
k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n
2.Probability of i'th item in reservoir finally is that of getting chosen at its round and never getting chosen later:
k/i * i/(i + 1) * ... * (n-1)/n = k/n
I'm sure reservoir sampling is very useful, and I'm just glad that I didn't waste too much time on trying to come up with such an efficient solution myself :-)
@vogelkaka Me too
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.