398. Random Pick Index

  • 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.

1
2
3
4
5
6
7
8
9
10
Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

方法一:

rand函数的用法

如果等概率的去选择一个数字

我的代码实现:

Oct 21, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
vector<int> _nums;
public:
Solution(vector<int> nums) {
_nums = nums;
}

int pick(int target) {
int index=0, n=0;
for(int i=0; i<_nums.size(); i++){
if(_nums[i]==target){
if(n==0){
n = 1;
index = i;
}else{
++n;
if(rand()%n==0)
index = i;
}
}
}
return index;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
vector<int> _nums;
public:
Solution(vector<int> nums) {
_nums = nums;
}

int pick(int target) {
int n = 0, ans = -1;
for(int i=0; i<_nums.size(); i++){
if(_nums[i]!=target)
continue;
if(n==0){
ans = i;
++n;
}
else{
++n;
if(rand()%n==0)
ans = i;
}
}
return ans;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
vector<int> _nums;
public:
Solution(vector<int> nums) {
_nums = nums;
}

int pick(int target) {
int n = 0, ans = -1;
for(int i = 0 ; i < _nums.size(); i++){
if(_nums[i] != target) continue;
if(n == 0){ans = i; n++;}
else{
n++;
if(rand() % n == 0){ans = i;}// with prob 1/(n+1) to replace the previous index
}
}
return ans;
}
};
谢谢你,可爱的朋友。