题目

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例: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);

解题思路分析

1、哈希辅助；时间复杂度O(1)，空间复杂度O(n)

type Solution struct {	m map[int][]int	r *rand.Rand}func Constructor(nums []int) Solution {	res := Solution{		m: make(map[int][]int),		r: rand.New(rand.NewSource(time.Now().Unix())),	}	for i := 0; i < len(nums); i++ {		res.m[nums[i]] = append(res.m[nums[i]], i)	}	return res}func (this *Solution) Pick(target int) int {	arr := this.m[target]	index := this.r.Intn(len(arr))	return arr[index]}

2、遍历；时间复杂度O(n)，空间复杂度O(n)

type Solution struct {	nums []int	r    *rand.Rand}func Constructor(nums []int) Solution {	return Solution{		nums: nums,		r:    rand.New(rand.NewSource(time.Now().Unix())),	}}func (this *Solution) Pick(target int) int {	res := 0	count := 1	for i := 0; i < len(this.nums); i++ {		if this.nums[i] == target {			// 蓄水池采样法			if this.r.Intn(count)+1 == count {				res = i			}			count++		}	}	return res}

Medium题目，考察蓄水池采样法