## 题目描述：

LeetCode 398. 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:

```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);
```

## Python代码：

``````class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type numsSize: int
"""
size = len(nums)
self.next = [0] * (size + 1)
for i, n in enumerate(nums):

def pick(self, target):
"""
:type target: int
:rtype: int
"""
cnt = 0
while idx > 0:
cnt += 1
idx = self.next[idx]
c = int(random.random() * cnt)
for x in range(c):
idx = self.next[idx]
return idx - 1
``````

Pingbacks已关闭。