Random Pick Index
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
Note
水槽采样
Reservior Sampling: when we get the Nth digit, we should generate 0-1 random number. if this random number is less than 1/N, we replace pre-digit to N. if random number is larger than 1/N, than keep pre-digit.
We should get 0-N random number and use 1 to decide replace or keep pre-digit.
Code
Last updated