LeetCode/solutions/398. Random Pick Index.md

# [398. Random Pick Index](https://leetcode.com/problems/random-pick-index/)

# 思路
给定一个包含重复数字的数组和一个target，要求随机返回一个target在数组中的下标。
题目指明我们不能用太多的空间，那我们可以考虑蓄水池采样（Reservoir Sampling）算法，这个算法我已经在[382题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/382.%20Linked%20List%20Random%20Node.md)中详细说过了，
这里不再赘述，直接给出代码。

pick时间复杂度O(n)，空间复杂度O(1)

# C++
```C++
class Solution {
private:
    vector<int>::iterator begin;
    int size;
public:
    Solution(vector<int>& nums) {
        begin = nums.begin();
        size = nums.size();
    }
    
    int pick(int target) {
        int res = -1, count = 1;
        
        for(int i = 0; i < size; i++){
            if(*(begin+i) != target) continue;
            if(rand() % count == 0) res = i;
            count++;
        }
        return res;
    }
};
```