随机数索引
难度：中等
遍历数组nums，构建一个map，key为数组元素，value为一个数组，数组中存放该元素出现的下标。调用pick方法获取索引时，随机一个数组下标，返回即可。
代码如下：
public class RandomPickIndex {
Map<Integer,List<Integer>> map ;
Random random = new Random();
public RandomPickIndex(int[] nums) {
map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])){
map.put(nums[i],new ArrayList<>());
}
map.get(nums[i]).add(i);
}
}
public int pick(int target) {
List<Integer> list = map.get(target);
return list.get(random.nextInt(list.size()));
}
}
执行结果不佳，改用蓄水池法解决问题
class RandomPickIndex {
int[] _nums;
Random random = new Random();
public RandomPickIndex(int[] nums) {
_nums = nums;
}
public int pick(int target) {
int res = 0;
int cnt = 0;
for(int i = 0;i < _nums.length;i++){
if(_nums[i]==target){
cnt++;
if(random.nextInt(cnt)==0){
res = i;
}
}
}
return res;
}
}
