# 398. Random Pick Index 随机数索引

@TOC

## # 题目描述

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
"""
self.nums = nums

def pick(self, target):
"""
:type target: int
:rtype: int
"""
idxs = []
for i, num in enumerate(self.nums):
if num == target:
idxs.append(i)
return idxs[random.randint(0, len(idxs) - 1)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)
``````

### # 字典保存索引

C++代码如下：

``````class Solution {
public:
Solution(vector<int> nums) {
for (int i = 0; i < nums.size(); ++i) {
m_[nums[i]].push_back(i);
}
}

int pick(int target) {
auto v = m_[target];
int s = v.size();
int i = rand() % s;
return v[i];
}
private:
unordered_map<int, vector<int>> m_;
};

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

### # 蓄水池抽样

C++代码如下：

``````class Solution {
public:
Solution(vector<int> nums) : nums_(nums) {
}

int pick(int target) {
int cnt = 0;
int res = -1;
for (int i = 0; i < nums_.size(); ++i)  {
int n = nums_[i];
if (n != target) continue;
++cnt;
if (rand() % cnt == 0)
res = i;
}
return res;
}
private:
vector<int> nums_;
};

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

http://www.cnblogs.com/grandyang/p/5875509.html https://www.cnblogs.com/snowInPluto/p/5996269.html

## # 日期

2018 年 3 月 13 日 2019 年 2 月 26 日 —— 二月就要完了