題目

給定一個可能含有重複元素的整數陣列，要求隨機輸出給定的數字的索引。 您可以假設給定的數字一定存在於陣列中。

注意：陣列大小可能非常大。 使用太多額外空間的解決方案將不會透過測試。

示例: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題目，考察蓄水池取樣法