1.题目
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
2.示例
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);
3.思路及代码
不推荐(可以增加对map使用的熟练程度)
// Solution 根据题意自定义类型，用来保存键(int类型,题目所给数组中的数字)值(切片,用来放下标们)对 type Solution map[int][]int // Constructor 遍历数组,将每个数字和对应下标以键值对的方式存入pos func Constructor(nums []int) Solution { pos := map[int][]int{} for i, v := range nums { //map的键是唯一的,面对重复的数字append只会多记录一条对应的下标 //比如{1,2,3,3,3}中3的值键值对为 3:[2 3 4] pos[v] = append(pos[v], i) } return pos } // Pick 最后根据键(所给数字)找对应的值(保存下标们的切片) // 再从找到的切片中返回其中的一个索引,用rand.Intn(len(indices))实现每个索引的返回概率应该相等 func (pos Solution) Pick(target int) int { indices := pos[target] return indices[rand.Intn(len(indices))] }
较推荐(思路清晰且效率高)
type Solution []int func Constructor(nums []int) Solution { return nums } func (nums Solution) Pick(target int) (ans int) { //创建了用来存放下标的切片 var find []int for i, num := range nums { if num == target { find = append(find, i) } } if len(find)==1 { //题目说可以假设给定的数字一定存在于数组中,所以只有一个是0 return find[0] }else { //题目说可以假设给定的数字一定存在于数组中,所以len(find)>0 return find[rand.Intn(len(find))] } }
推荐(水塘抽样法，效率高且可以解决更特殊的问题)
type Solution []int func Constructor(nums []int) Solution { return nums } func (nums Solution) Pick(target int) (ans int) { //没有创建切片 count := 0 for i, num := range nums { if num == target { //遇到目标数字的次数+1 count++ //以下就是水塘抽样需要理解的地方 //每次遇到目标数字都生成一个0到遇到次数之间的随机数 //如果是0我愿称之为命中，那么ans被暂时设为这个num的下标 //如果后面再也没有被命中的数字,那么ans就会被返回了 if rand.Intn(count) == 0 { ans = i } } } return }
很容易理解哪个数会被返回是随机的,但是不是如题目所说每个数返回的概率都相等呢？
官方证明如下：
学过概率论应该不难理解。
第三种和第二种思路一样，只是在输出一个随机的下标的方式上有所不同。
第三种有一点难理解却是最推荐的解法，原因其实在题目的注意里有提到：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
前两种方法都有创建切片，不过也通过了。
但是在面对"不允许创建切片"或者"在不知道文件总行数的情况下，如何从文件中随机的抽取一行？"这种问题时，水塘抽样就香香了。
