Random Pick Index
Reservoir Sampling
Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Note: The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:
Analysis
To those who don't understand why it works. Consider the example in the OJ {1,2,3,3,3} with target 3,you want to select 2,3,4 with a probability of 1/3 each.
2 : It's probability of selection is 1 * (1/2) * (2/3) = 1/3 3 : It's probability of selection is (1/2) * (2/3) = 1/3 4 : It's probability of selection is just 1/3
利用均匀分布的随机数:
代表了 k / count的概率新的index i
会替换已有的sample。
(1 / i) * (1 - 1/ (i + 1)) * (1 - 1/(i + 2)) * ... * (1 - 1 / n) = 1/n
Solution
Reservoir Sampling
121 ms, faster than 94.95%
Reference
https://leetcode.com/problems/random-pick-index/discuss/88072/Simple-Reservoir-Sampling-solution
Last updated