Leetcode 398. 随机数索引
题目
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);
题解
我们用一个数组存储所有数，然后查找时，第一次查找到，我们令答案等于下标；之后再查找到，我们生成一个随机数，如果能整除这个数当前重复次数，则进行替换。详细过程见代码
代码
class Solution {
public:
vector
<int>& nums
;
Solution(vector
<int>& nums
):nums(nums
) {
}
int pick(int target
) {
int n
= nums
.size();
int cnt
=0;
int choice
;
for(int i
=0; i
<n
; i
++){
if(nums
[i
] == target
){
cnt
++;
if(cnt
== 1) choice
= i
;
else if(rand() % cnt
== 0) choice
= i
;
}
}
return choice
;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/random-pick-index 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
