问题描述：
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);
解题思路：
这道题要求我们随机返回一个给定目标数字的下标。
并且数组可能十分之大而我们不能用过多的额外空间。
这个时候可以用水塘抽样算法来解决
当我们遇见一个数字等于target时，total++。
同时判断是否取当前数字。
我们通过rand()随机生成一个数字，使之对total求余，若余数为0，则替换，否则不替换
代码：
class Solution { public: Solution(vector<int> nums) { v = nums; } int pick(int target) { int ret = 0; int total = 0; for(int i = 0; i < v.size(); i++){ if(v[i] == target){ total++; int res = rand() % total; if(res == 0) ret = i; } } return ret; } private: vector<int> v; }; /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int param_1 = obj.pick(target); */
原文：https://www.cnblogs.com/yaoyudadudu/p/9275894.html