README
¶
蓄水池抽样问题
首先从最简单的例子出发：数据流只有一个数据。我们接收数据，发现数据流结束了，直接返回该数据，该数据返回的概率为1。
看来很简单，那么我们试试难一点的情况：假设数据流里有两个数据。我们读到了第一个数据，这次我们不能直接返回该数据，因为数据流没有结束。我们继续读取第二个数据，发现数据流结束了。因此我们只要保证以相同的概率返回第一个或者第二个数据就可以满足题目要求。因此我们生成一个0到1的随机数R,如果R小于0.5我们就返回第一个数据，如果R大于0.5，返回第二个数据。
接着我们继续分析有三个数据的数据流的情况。为了方便，我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2和前面的例子一样，我们只能保存一个数据，所以必须淘汰1和2中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一的概率淘汰一个，例如我们淘汰了2。继续读取流中的数据3，发现数据流结束了，我们知道在长度为3的数据流中，如果返回数据3的概率为1/3,那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3两个数据，我们通过一次随机选择，以1/3的概率留下数据3，以2/3的概率留下数据1。那么数据1被最终留下的概率是多少呢？
数据1被留下：（1/2）(2/3) = 1/3 数据2被留下概率：（1/2）(2/3) = 1/3 数据3被留下概率：1/3 这个方法可以满足题目要求，所有数据被留下返回的概率一样！
因此，我们做一下推论：
假设当前正要读取第n个数据，则我们以1/n的概率留下该数据，否则留下前n-1个数据中的一个。
作者：an-xin-9 链接：https://leetcode-cn.com/problems/random-pick-index/solution/xu-shui-chi-chou-yang-wen-ti-by-an-xin-9/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Documentation
¶
Overview ¶
* @lc app=leetcode id=398 lang=golang * * [398] Random Pick Index * * https://leetcode.com/problems/random-pick-index/description/ * * algorithms * Medium (53.02%) * Likes: 354 * Dislikes: 564 * Total Accepted: 70.4K * Total Submissions: 132.7K * Testcase Example: '["Solution","pick"]\n[[[1,2,3,3,3]],[3]]' * * Given an array of integers with possible duplicates, randomly output the * index of a given target number. You can assume that the given target number * must exist in the array. * * Note: * The array size can be very large. Solution that uses too much extra space * will not pass the judge. * * Example: * * * int[] nums = new int[] {1,2,3,3,3}; * Solution solution = new Solution(nums); * * // pick(3) should return either index 2, 3, or 4 randomly. Each index should * have equal probability of returning. * solution.pick(3); * * // pick(1) should return 0. Since in the array only nums[0] is equal to 1. * solution.pick(1); * *
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Source Files