• 43.4%

https://leetcode.com/problems/random-pick-index/description/

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.

rand函数的用法

Oct 21， 2017

C++_Time: O(n), Space: O(n)_116ms_96.41%_with clear explanation by probability

Actually, we could first consider following question:

You have a file consisting of characters. The characters in the file can be read sequentially, but the length of the file is unknown. How do you pick a character so that every character in the file has equal probability of being chosen?

For this problem we can take algorithm like this:

• Draw the 1st char. If there is a second char, then we will hold 1st char by prob = 1/2, and replace the 1st char to 2nd char with prob = 1/2. After this step we suppose that the char is X now.

• After then, if there is 3rd char, then we will hold the X with prob = 2/3 and replace X to 3rd char with prob = 1/3. Why do they hold the same prob to be picked?

Because:
Obviously, Prob(the 3rd char is picked) = 1/3;
Prob(the 2nd char is picked) = 1 1/2 2/3 = 1/3;
Prob(the 1st char is picked) = 1 1/2 2/3 = 1/3;

• So we can say that when we now has n chars and there is still another char in the file, we can pick the other char with prob= 1/(n+1), also keep original char with prob = n/(n+1), then we can secure each char is picked with same prob = 1/(n+1), because prob = 1 1/2 2/3 ···· n/(n+1) = 1/(n+1).

Now, go back to this problem. The thought is the same, when we meet some nums[i] == target, we can use above conclusion: we can pick the other char with prob= 1/(n+1), also keep original char with prob = n/(n+1), then we can secure each char is picked with same prob = 1/(n+1).

Code: